Party Lemonade

题意 没有柠檬水的新年派对不是新年派对。像往常一样，你期待着客人，而柠檬水已经成为一种令人愉快的必需品。 你最喜欢的商店卖 n 种不同价格的装在不同瓶子里的柠檬水。一瓶第 i 种柠檬水，体积为2^{i-1}，价格为c_{i}卢布。商店里的每种柠檬水可以被认为有无限瓶。 你想要买至少 L 升的柠檬水，你需要花费多少卢布？ 输入格式： 第一行包含两个整数 n 和 L（1<=n<=30;1<=L<=10^{9}）。 第二行包含 n 个整数c_{1},c_{2},...,c_{n}（1<=c_{i}<=10^{9}）。 输出格式： 输出一个正整数---买至少 L 升的柠檬水，你需要支付的最少卢布。 Translated by Fowany

A New Year party is not a New Year party without lemonade! As usual, you are expecting a lot of guests, and buying lemonade has already become a pleasant necessity. Your favorite store sells lemonade in bottles of $ n $ different volumes at different costs. A single bottle of type $ i $ has volume $ 2^{i-1} $ liters and costs $ c_{i} $ roubles. The number of bottles of each type in the store can be considered infinite. You want to buy at least $ L $ liters of lemonade. How many roubles do you have to spend?

The first line contains two integers $ n $ and $ L $ ( $ 1<=n<=30 $ ; $ 1<=L<=10^{9} $ ) — the number of types of bottles in the store and the required amount of lemonade in liters, respectively. The second line contains $ n $ integers $ c_{1},c_{2},...,c_{n} $ ( $ 1<=c_{i}<=10^{9} $ ) — the costs of bottles of different types.

Output a single integer — the smallest number of roubles you have to pay in order to buy at least $ L $ liters of lemonade.

4 12
20 30 70 90

150

4 3
10000 1000 100 10

10

4 3
10 100 1000 10000

30

5 787787787
123456789 234567890 345678901 456789012 987654321

44981600785557577

In the first example you should buy one 8-liter bottle for 90 roubles and two 2-liter bottles for 30 roubles each. In total you'll get 12 liters of lemonade for just 150 roubles. In the second example, even though you need only 3 liters, it's cheaper to buy a single 8-liter bottle for 10 roubles. In the third example it's best to buy three 1-liter bottles for 10 roubles each, getting three liters for 30 roubles.