R3D3 花了一些时间在 MDCS 实习。赚到足够的钱后,他决定去很远很远的地方度假。他喜欢晒黑、喝不含酒精的鸡尾酒以及参加当地流行乐队的音乐会。在听“The White Buttons”和他们的热门歌曲“Dacan the Baker”时,他遇到了另一个机器人,他确信他是他一生的挚爱。好吧,至少是他的夏天。无论如何,R3D3 太害羞而不敢接近他潜在的灵魂伴侣,所以他决定给她写一封情书。然而,他却发现了一个问题。由于恐怖威胁,星际空间警察正在监视在该地区发送的所有信件。因此,R3D3 决定发明自己的字母表,他确信他的爱人能够破译这个字母表。
R3D3的字母表中有n个字母,他想将每个字母表示为“0”和“1”的序列,这样就没有一个字母序列是另一个字母序列的前缀。由于星际空间通信服务最近对发明的字母表征税,R3D3 必须为其字母表代码中的每一位支付一定数量的钱(请检查示例测试以获取说明)。他太痴情了,无法清晰地思考,所以他向你求助。
分别给定 R3D3 字母表中每个“0”和“1”的成本 c0 和 c1,您应该以最小的总成本对字母表进行编码(具有上述属性)。
输入
输入的第一行包含三个整数 n (2 ≤ n ≤ 108)、c0 和 c1 (0 ≤ c0, c1 ≤ 108) - 字母表中的字母数以及“0”和“1”的成本。
输出
输出一个整数——整个字母表的最小可能总成本。
示例
输入 #1
4 1 2
输出 #1
12
注意
字母表中有 4 个字母。最佳编码是“00”、“01”、“10”、“11”。使用了 4 个 0 和 4 个 1,因此总成本为 4·1 + 4·2 = 12。