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.
#Abhigyan Khaund - syl
# n = int(raw_input())
# m = int(raw_input())
n,l = map(int, raw_input().split())

c = map(int, raw_input().split())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def lcm(a,b):
	return (a*b)/gcd(a,b)


def bin_exp(x, n):
	if(n==0):
		return 1
	elif(n%2==0):
		return bin_exp(x*x,n/2)
	else:
		return x*bin_exp(x*x, (n-1)/2)

k = n-1
ans = 0
# lc = bin_exp(2,n-1)
# new_arr = []
# for i in range(0,len(c)):
# 	new_arr.append([c[i]*lc,i])
# 	lc/=2
# m = min(new_arr)
# count = l/(2**m[1])
# if(count==0):
# 	ans += m[0]
# 	l-=2**i
# else:
# 	ans+=count*m[0]
# 	l=l%(2**m[1])
# print l,ans,new_arr
temp =set([])
while l>0:
	new_arr = []
	val = []
	for i in range(n):
		co = l/bin_exp(2,i)
		if(co!=0):
			new_arr.append([co*c[i],co*bin_exp(2,i)])
			val.append(c[i]/(1.0*bin_exp(2,i)))
		else:
			# val.append(c[i]/(1.0*bin_exp(2,i)))
			new_arr.append([1*c[i],bin_exp(2,i)])
			temp.add(ans+c[i])
	m = min(val)
	ind = val.index(m)
	m = new_arr[ind]
	ans+=m[0]
	l-=m[1]
	# print new_arr,ans
	# print
	# print m,l,new_arr
if(len(temp)>0):
	print min(ans,min(temp))
else:
	print ans 