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 2i - 1 liters and costs ci 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 c1, c2, ..., cn (1 ≤ ci ≤ 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.

Examples

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.
import functools
import math

def compare(a,b):
	A=a[0]/a[1]
	B=b[0]/b[1]

	if A < B:
		return -1
	if A > B:
		return 1
	if(A==B):
		if a[1]>b[1]:
			return -1
		else:
			return 1
	


n,L =input().split()
n= int(n)
L = int(L)
a = [int(x) for x in input().split()]
v = []

for i in range(n):
	if i==0:
		v.append([a[i],math.pow(2,i)])
	else:
		a[i] = min(a[i],2*a[i-1])
		v.append([a[i],math.pow(2,i)])
		
#print(v)
v = sorted(v, key=functools.cmp_to_key(compare))
#print(v)

def solve(dp,L,m):
	for i in range(len(dp)):
		if dp[i][0]<=m:
			pp=m//dp[i][0]
			m-=(dp[i][0]*pp)
			L-=(dp[i][1]*pp)
			if L <= 0:
				return True
	if L<=0 :
		return True
	else:
		return False
l = 1
r = 10000000000000000000
res= r

while l <= r:
	if l == r:
		if solve(v,L,l):
			res=min(res,l)
		break
	else:
		m = (l+r)//2;
		if solve(v,L,m) == True:
			res=min(res,m)
			r=m-1
		else:
			l=m+1

print(res)