分数: 466 分
问题陈述
高桥将浇灌他的田地 N 天。每天,他都会选择并执行两种浇水方法中的一种。
方法A 是一种一次性喷洒大量水的方法。当选择这个方法的那一天,基本上会产生增长量 a,但由于浇水太多,土壤变得渍水,在上面获得的生长量 第二天 减半(此后的日子没有影响)。
方法B 是一种小心地撒少量水的方法。当选择这个方法的那一天,基本上会产生增长量 b。由于对土壤没有任何负担,因此对第二天不会产生负面影响。
具体来说,每天的增长量由以下规则确定:
- 如果前一天使用了方法B,或者是第一天(不存在前一天),则不会发生减半。如果选择方法A,则增长量为 a;如果选择方法B,则增长量为 b.
- 如果前一天使用方法 A,当日成长量减半。如果选择方法A,则增长量为 \lfloor a / 2 \rfloor;如果选择方法B,则增长量为 \lfloor b / 2 \rfloor。在这里, \lfloor x \rfloor 表示不超过的最大整数 x.
减半始终应用于基值 a or b。前一天的增长量是否减半并不重要;该决定仅基于“前一天是否使用了方法 A”。例如,如果连续三天选择方法A,则增长量为 a 第一天, \lfloor a/2 \rfloor 第二天,以及 \lfloor a/2 \rfloor 第三天。
求浇水方式超过时的最大可能总生长量 N 天是最佳选择的。
约束
- 1 \leq N \leq 10^{18}
- 1 \leq a \leq 10^9
- 1 \leq b \leq 10^9
- 所有输入值均为整数。
输入
N a b
- 第一行包含天数 N,方法A的基础生长量 a,以及方法B的基础生长量 b,以空格分隔。
输出
在一行中输出最大可能的总生长量。
示例输入 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