E - 畑の水やり計画 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は N 日間にわたって畑の水やりを行います。毎日、2 種類の水やり方法のうちどちらか 1 つを選んで実行します。

方法 A は大量の水を一気にまく方法です。この方法を選んだ日は基本的に a の成長量を得られますが、水をまきすぎるため土壌が水浸しになり、翌日に得られる成長量が半減してしまいます（翌々日以降への影響はありません）。

方法 B は少量の水をじっくりまく方法です。この方法を選んだ日は基本的に b の成長量を得られます。土壌への負担がないため、翌日への悪影響はありません。

具体的には、各日の成長量は以下のルールで決まります。

  • 前日に方法 B を実行していた場合、または 1 日目（前日が存在しない）の場合、半減は発生しない。方法 A を選んだなら成長量は a、方法 B を選んだなら成長量は b である。
  • 前日に方法 A を実行していた場合、その日の成長量は半減する。方法 A を選んだなら成長量は \lfloor a / 2 \rfloor、方法 B を選んだなら成長量は \lfloor b / 2 \rfloor となる。ここで \lfloor x \rfloor は x 以下の最大の整数を表す。

半減は常に基本の値 a または b に対して適用されます。前日の成長量が半減されていたかどうかは関係なく、「前日に方法 A を実行したかどうか」のみで判定します。たとえば、3 日連続で方法 A を選んだ場合、1 日目の成長量は a、2 日目の成長量は \lfloor a/2 \rfloor、3 日目の成長量も \lfloor a/2 \rfloor です。

N 日間の水やり方法を最適に選んだとき、成長量の合計の最大値を求めてください。

制約

  • 1 \leq N \leq 10^{12}
  • 1 \leq a \leq 10^5
  • 1 \leq b \leq 10^5
  • 入力はすべて整数である。

入力

N a b
  • 1 行目には、水やりを行う日数 N、方法 A の基本成長量 a、方法 B の基本成長量 b が、スペース区切りで与えられる。

出力

成長量の合計の最大値を 1 行で出力せよ。

入力例 1

5 10 3

出力例 1

32

入力例 2

4 3 5

出力例 2

20

入力例 3

100 100 51

出力例 3

6276

入力例 4

1000000000000 100000 1

出力例 4

50000000000050000

入力例 5

1 1 1

出力例 5

1

Score : 466 pts

Problem Statement

Takahashi will water his field over N days. Each day, he chooses and executes exactly one of two watering methods.

Method A is a method that spreads a large amount of water all at once. On a day when this method is chosen, it basically yields a growth amount of a, but because too much water is spread, the soil becomes waterlogged, and the growth amount obtained on the next day is halved (there is no effect on days after that).

Method B is a method that carefully spreads a small amount of water. On a day when this method is chosen, it basically yields a growth amount of b. Since there is no burden on the soil, there is no negative effect on the next day.

Specifically, the growth amount for each day is determined by the following rules:

  • If Method B was used on the previous day, or if it is the first day (no previous day exists), no halving occurs. If Method A is chosen, the growth amount is a; if Method B is chosen, the growth amount is b.
  • If Method A was used on the previous day, the growth amount for that day is halved. If Method A is chosen, the growth amount is \lfloor a / 2 \rfloor; if Method B is chosen, the growth amount is \lfloor b / 2 \rfloor. Here, \lfloor x \rfloor denotes the largest integer not exceeding x.

The halving is always applied to the base values a or b. It does not matter whether the previous day's growth amount was itself halved; the determination is based solely on "whether Method A was used on the previous day." For example, if Method A is chosen for three consecutive days, the growth amounts are a on the first day, \lfloor a/2 \rfloor on the second day, and \lfloor a/2 \rfloor on the third day.

Find the maximum possible total growth amount when the watering methods over the N days are chosen optimally.

Constraints

  • 1 \leq N \leq 10^{18}
  • 1 \leq a \leq 10^9
  • 1 \leq b \leq 10^9
  • All input values are integers.

Input

N a b
  • The first line contains the number of days N, the base growth amount of Method A a, and the base growth amount of Method B b, separated by spaces.

Output

Output the maximum possible total growth amount in a single line.

Sample Input 1

5 10 3

Sample Output 1

32

Sample Input 2

4 3 5

Sample Output 2

20

Sample Input 3

100 100 51

Sample Output 3

6276

Sample Input 4

1000000000000 100000 1

Sample Output 4

50000000000050000

Sample Input 5

1 1 1

Sample Output 5

1