没有柠檬水的新年聚会不是新年聚会!和往常一样,你迎来了很多客人,买柠檬水已经成为一种愉快的必需品。
您最喜欢的商店以不同的价格出售 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 卢布。