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.
#JMD
#Nagendra Jha-4096

 
import sys
import math

#import fractions
#import numpy
 
###File Operations###
fileoperation=0
if(fileoperation):
    orig_stdout = sys.stdout
    orig_stdin = sys.stdin
    inputfile = open('W:/Competitive Programming/input.txt', 'r')
    outputfile = open('W:/Competitive Programming/output.txt', 'w')
    sys.stdin = inputfile
    sys.stdout = outputfile

###Defines...###
mod=1000000007
 
###FUF's...###

def check(n,x,l):
    tot=0
    while(1):
        flag=1
        i=0
        while(i<len(v)):
            c=int(v[i][1]*v[i][0])
            if(c<=x):
                cnt=x//c
                x-=cnt*c
                tot+=v[i][1]*cnt
                flag=0
                break
            else:
                i+=1
        if(tot>=l):
            return 1
        if(flag):
            break
    return 0
    
    
    
    
def getkey(item):
	return item[0]

def nospace(l):
    ans=''.join(str(i) for i in l)
    return ans
v=[]
 
##### Main ####
t=1
for tt in range(t):
    n,l=map(int, sys.stdin.readline().split(' '))
    aa=list(map(int,sys.stdin.readline().split(' ')))
    for i in range(n):
    	val=1<<i
    	a=aa[i]
    	v.append([a/val,val])
    v=sorted(v,key=getkey)
    ans=10000000000000000000000000000000
    low=0
    high=ans
    while(low<=high):
        mid=(low+high)//2
        if(check(n,mid,l)):
            high=mid-1
            ans=min(ans,mid)
        else:
            low=mid+1
    print(ans)
    #n,k,s= map(int, sys.stdin.readline().split(' '))
    #a=list(map(int,sys.stdin.readline().split(' ')))
    
    
#####File Operations#####
if(fileoperation):
    sys.stdout = orig_stdout
    sys.stdin = orig_stdin
    inputfile.close()
    outputfile.close()