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.
def merge(a,b):
    c = []
    while len(a) != 0 and len(b) != 0:
        if a[0][0] < b[0][0]:
            c.append(a[0])
            a.remove(a[0])
        else:
            c.append(b[0])
            b.remove(b[0])
    if len(a) == 0:
        c += b
    else:
        c += a
    return c

def mergesort(x):
    
    if len(x) == 0 or len(x) == 1:
        return x
    else:
        middle = len(x)//2
        a = mergesort(x[:middle])
        b = mergesort(x[middle:])
        return merge(a,b)

def get_int_list(string):
	ls = []
	sum = ''
	for s in string:
		if s == ' ':
			ls.append(int(sum))
			sum = ''
		else:
			sum += s
	ls.append(int(sum))
	return ls
	
def get_ans(l, ls2):
	cost = 0
	while l > 0:
		if l <= ls2[0][1]:
			price = cost + ls2[0][2]
			if len(ls2) > 1:
				ls2.pop(0)
				cost = min(price, cost + get_ans(l, ls2))
			else:
				cost = price
			break
		else:
			num = l // ls2[0][1]
			l -= ls2[0][1] * num
			cost += num * ls2[0][2]
			#print('\nelse', cost, num, l)
			
			#print(ls2)
		
	return cost
	
x = input().split()
n = int(x[0])
l = int(x[1])

ls = get_int_list(input())

ls2 = []

for i in range(1, n + 1):
	vol = 2 ** (i - 1)
	unit = ls[i - 1] / vol
	ls2.append([unit, vol, ls[i - 1]])
	#ls3.append([vol, ls[i - 1]])
	
ls2 = mergesort(ls2)
#ls3 = mergesort(ls3)
cost = 0
#print(ls2);print()

		
print(get_ans(l, ls2))
	
