← 返回题目列表

Codeforces · 913/C

C. 派对柠檬水

中文机器翻译题面 查看原题

没有柠檬水的新年聚会不是新年聚会!和往常一样,你迎来了很多客人,买柠檬水已经成为一种愉快的必需品。

您最喜欢的商店以不同的价格出售 n 瓶不同容量的柠檬水。一瓶 i 型的容量为 2i - 1 升,价格为 ci 卢布。商店里每种类型的瓶子数量可以认为是无限的。

您想购买至少 L 升柠檬水。您需要花费多少卢布?

输入

第一行包含两个整数 n 和 L (1 ≤ n ≤ 30; 1 ≤ L ≤ 109) - 分别是商店中瓶子的类型数量和所需的柠檬水量(以升为单位)。

第二行包含 n 个整数 c1, c2, ..., cn (1 ≤ ci ≤ 109) – 不同类型瓶子的成本。

输出

输出一个整数 - 购买至少 L 升柠檬水所需支付的最小卢布数。

示例

输入 #1

4 12
20 30 70 90

输出 #1

150

输入 #2

4 3
10000 1000 100 10

输出 #2

10

输入 #3

4 3
10 100 1000 10000

输出 #3

30

输入#4

5 787787787
123456789 234567890 345678901 456789012 987654321

输出#4

44981600785557577

注意

在第一个示例中,您应该以 90 卢布的价格购买一瓶 8 升的瓶子,并以每瓶 30 卢布的价格购买两瓶 2 升的瓶子。总共只需 150 卢布即可获得 12 升柠檬水。

在第二个示例中,即使您只需要 3 升,但花 10 卢布购买一瓶 8 升的瓶子更便宜。

在第三个示例中,最好以每个 10 卢布的价格购买三个 1 升的瓶子,3 升的价格为 30 卢布。