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?

Input

The first line contains two integers n and L (1 ≤ n ≤ 30; 1 ≤ L ≤ 109) — 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 ≤ 109) — the costs of bottles of different types.

Output

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

Example

Input

4 12
20 30 70 90

Output

150

Input

4 3
10000 1000 100 10

Output

10

Input

4 3
10 100 1000 10000

Output

30

Input

5 787787787
123456789 234567890 345678901 456789012 987654321

Output

44981600785557577

Note

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.

题意 ： 给你 n 个物品，以及一个容器的体积 l , n 个物品的体积是 2^i-1 ， 求在超过容器体积的前提下，最小的花费是多少。

思路分析 ： 想了一个贪心策略，优先去贪性价比最高的物品，当恰好装下的时候，此时可以记录一下答案，若不能时，此时可以让他们多装一个，再次记录一下答案，深搜就行了

代码示例：

/*
* Author: parasol
* Created Time: 2018/3/7 18:18:10
* File Name: 2.cpp
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

struct node
{
ll l, c;
double p;
bool operator< (const node &v)const{
return p < v.p;
}
}pre[35];
ll n, l;
ll ans = __LONG_LONG_MAX__;

void dfs(ll x, ll cost, ll sum){
if (cost >= ans) return;
if (sum <= 0) {ans = min(ans, cost); return;}
if (x == n+1) return;
ll f = sum / pre[x].l;
int pt = 0;
if (sum%pre[x].l == 0){
ans = min(ans, cost+f*pre[x].c);
return;
}
else {
dfs(x+1, cost+(f+1)*pre[x].c, sum-(f+1)*pre[x].l);
pt = 1;
}
if (pt) {
dfs(x+1, cost+f*pre[x].c, sum-f*pre[x].l);
}
}

int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> l;
ll an = 1;
for(ll i = 1; i <= n; i++){
scanf("%lld", &pre[i].c);
pre[i].l = an;
pre[i].p = 1.0*pre[i].c/an;
an *= 2;
}
sort(pre+1, pre+1+n);
dfs(1, 0, l);
printf("%lld\n", ans);
return 0;
}