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 heapq

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

def heuristic(remaining, lowest_cost_per_liter):
    return remaining * lowest_cost_per_liter

def neighbors(remaining, costs):
    # We only have 2 actual neighbors - the lowest cost per liter that is still
    # under remaining, and the lowest total cost that is over it (if it exists)
    lowest_cost_per_liter, cost, power = min(
        ((cost / 2 ** power, cost, power) for power, cost in enumerate(costs) if 2 ** power <= remaining)
    )

    # Do the same optimization we did at the start...
    new_liters = 2 ** power
    new_cost = cost * (remaining // new_liters)
    new_remaining = remaining % new_liters
    yield (new_remaining, new_cost)

    lowest_cost_total = min(
        (cost for power, cost in enumerate(costs) if 2 ** power >= remaining),
        default=None
    )
    
    if lowest_cost_total is not None:
        yield (0, lowest_cost_total)

def a_star(L, costs):
    lowest_cost_per_liter = min(cost / 2 ** power for power, cost in enumerate(costs))

    # State is (h, remaining)
    g_score = {}
    g_score[L] = 0

    f_score = {}
    f_score[L] = heuristic(L, lowest_cost_per_liter)

    open_queue = [(f_score[L], L)]
    open_set = {L}

    while len(open_queue) > 0:
        current_f, current_remaining = heapq.heappop(open_queue)

        if current_remaining == 0:
            return g_score[0]

        if current_remaining not in open_set:
            continue

        open_set.remove(current_remaining)
        for new_remaining, cost in neighbors(current_remaining, costs):
            # print(new_remaining, cost)
            new_g_score = g_score[current_remaining] + cost
            if new_remaining not in g_score or new_g_score < g_score[new_remaining]:
                g_score[new_remaining] = new_g_score
                f_score[new_remaining] = new_g_score + heuristic(new_remaining, lowest_cost_per_liter)

                heapq.heappush(open_queue, (f_score[new_remaining], new_remaining))

                if new_remaining not in open_set:
                    open_set.add(new_remaining)
    
    return None

# A quick optimization - we can assume we'll always use the lowest cost per liter
# when available.
lowest_cost_per_liter, cost, power = min((cost / 2 ** power, cost, power) for power, cost in enumerate(costs))
liters = 2 ** power

start_cost = cost * (L // liters)
L = L % liters

print(start_cost + a_star(L, costs))

	  			  	     	  	     			 	