题目描述

Sophie 被姑姑派去买柠檬水，小卖部供应 $N$ 种不同容量包装的柠檬水：第 $i$ 种包装容积为 $2^{i-1}$ 升，价钱为 $c_i$ 。每种柠檬水都可以认为是无限供应的。

Sophie 现在想总共买够至少 $L$ 升柠檬水，请求出她的最小花费。

输入格式

第一行包含 $2$ 个整数 $N$ 和 $L$，意义见问题描述。

第二行包含 $N$ 正整数 $c_i$，代表第 $i$ 种柠檬水的价钱。

输出格式

输出一个正整数，代表买够至少 $L$ 升柠檬水所需要的最小花费。

输入输出样例 #1

输入 #1

4 12
20 30 70 90

输出 #1

150

输入输出样例 #2

1输入 #2

4 3
10000 1000 100 10

输出 #2

10

输入输出样例 #3

输入 #3

5 787787787
123456789 234567890 345678901 456789012 987654321

输出 #3

44981600785557577

说明/提示

对于 $20\%$ 的数据，$1 \leq N \leq 10, 1 \leq c_i \leq 100, 1 \leq L \leq 1000$

对于 $60\%$ 的数据，$1 \leq N \leq 20, 1 \leq c_i \leq 10^7, 1 \leq L \leq 10^7$

对于 $100\%$ 的数据，$1 \leq N \leq 30, 1 \leq c_i \leq 10^9, 1 \leq L \leq 10^9$