题目描述

新年派对要是没有柠檬水，那还叫什么新年派对！和往年一样，你又要招待一大堆客人，买柠檬水这事儿虽然麻烦，但也躲不掉。

你常去的那家店卖柠檬水，有 $n$ 种不同容量的瓶子，价格也各不相同。第 $i$ 种瓶子的容量是 $2^{i-1}$ 升，售价为 $c_i$ 卢布。店里每种瓶子都管够，要多少有多少。

你至少得买够 $L$ 升柠檬水。那么，你最少得花多少钱呢？

输入

第一行两个整数 $n$ 和 $L$（$1 \le n \le 30$，$1 \le L \le 10^9$），分别表示瓶子种类数和你需要的最少升数。

第二行 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le 10^9$），依次表示每种瓶子的价格。

输出

输出一个整数 —— 为了买到至少 $L$ 升柠檬水，你最少需要支付多少卢布。

提示

第一个样例里，买一个 8 升瓶（90 卢布）和两个 2 升瓶（每个 30 卢布），总共 12 升，只要 150 卢布，最划算。

第二个样例里，虽然你只要 3 升，但直接买一个 8 升瓶只要 10 卢布，比买小瓶便宜多了。

第三个样例里，最省钱的买法是三个 1 升瓶，每个 10 卢布，凑够 3 升，共花 30 卢布。

样例

样例 1

输入：

4 12
20 30 70 90

输出：

150

样例 2

输入：

4 3
10000 1000 100 10

输出：

10

样例 3

输入：

4 3
10 100 1000 10000

输出：

30

样例 4

输入：

5 787787787
123456789 234567890 345678901 456789012 987654321

输出：

44981600785557577