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.
#n different volumes
#bottle of type i has volume s ** (i - 1), costs c[i]
#buy at least L liters
#t32 = [123456789, 234567890, 345678901, 456789012, 987654321]
#t3 = [5, 787787787]
#t22 = [10, 100, 1000, 10000]#[::-1]
#t2 = [4, 3]
#t1 = [4, 12]
#t12 = [20, 30, 70, 90]
num_types, req_l = list(map(int, input().split()))
costs = [0]
costs.extend(map(int, input().split()))
if req_l == 0:
    print(0)
else:
    volumes = [0]
    for x in range(num_types):
        if 2 ** x <= req_l:
            volumes.append(2 ** x)
        else:
            break
    volume_len = len(volumes)
    extra_part = costs[volume_len:] + [999999999999999999999999999999]

    min_extra = min(extra_part)
    min_idx = extra_part.index(min_extra) + volume_len
    #print('MIN EXTRA', min_extra)
    costs = costs[:volume_len]

    best = 999999999999999999999999999
    for idx, v in enumerate(volumes):
        if idx == 0:
            continue
        new_best = costs[idx] / v
        if new_best < best:
            best = new_best
        else:
            costs[idx] = -1
    for i in range(len(volumes) - 1, -1, -1):
        if costs[i] < 0:
            costs[i:i+1] = []
            volumes[i:i+1] = []
    volume_len = len(volumes)
    #print('volumes', volumes)
    #print('costs', costs)
    out = []
    for i in range(volume_len - 1, -1, -1):
        if req_l > 0:
            needed = req_l // volumes[i]
            #print('req_l', req_l)
            #print('need', needed, 'vol', volumes[i], 'volt', volumes[i] * needed,'costing', costs[i] * needed)
            req_l -= volumes[i] * needed
            out.append((costs[i] * needed, costs[i] * (1 + needed)))
            #print('Remaining', req_l)
        else:
            out.append((0, costs[i]))
    prev = 999999999999999999999999999999
    running_total = 0
    for curr_contrib, override_cost in out[::-1]:
        #print(override_cost, curr_contrib)
        running_total += curr_contrib
        if override_cost < running_total:
            running_total = override_cost
    #print(out)
    #print('^^out')
    #print(req_l)
    #print('ANSWER')
    ans = min(running_total, min_extra)
    #if ans == min_extra:
    #        print('EXTRA USED')
    print(ans)
