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 2^{i} - 1 liters and costs c_{i} 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 ≤ 10^9) — the number of types of bottles in the store and the required amount of lemonade in liters, respectively.

The second line contains n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10^9) — 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.

Difficulty: interview

Starter code:

Solutions:
3
# Copyright (C) 2017 Sayutin Dmitry.
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License as
# published by the Free Software Foundation; version 3
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; If not, see <http://www.gnu.org/licenses/>.

def solve(a, l):
    if l == 0:
        return 0

    if l == 1:
        return a[0]
    
    k = 0
    while (2 ** k) < l:
        k += 1
    
    return min(a[k], a[k - 1] + solve(a, l - (2 ** (k - 1))))
    

def main():
    n, l = list(map(int, input().split()))
    a = list(map(int, input().split()))

    for i in range(n - 2, -1, -1):
        if a[i] > a[i + 1]:
            a[i] = a[i + 1]
    
    for i in range(1, n):
        if a[i] > 2 * a[i - 1]:
            a[i] = 2 * a[i - 1]

    while len(a) < 35:
        a.append(2 * a[len(a) - 1])

    #print(a)

    print(solve(a, l))
            
main()


import sys
input = sys.stdin.readline

n, L = map(int, input().split())
c = list(map(int, input().split()))
a = [c[0]]

for i in range(1, 31):
  cand = [a[-1] * 2]
  if i < n: cand.append(c[i])
  a.append(min(cand))

ans = []
sum = 0

for i in reversed(range(31)):
  if L <= (1<<i):
    ans.append(sum + a[i])
  else:
    L -= (1<<i)
    sum += a[i]
  
print(min(ans))

n, m = map(int, input().split())
l = [int(x) for x in input().split()]
for i in range(1, n):
    l[i] = min(l[i], 2*l[i - 1])
c = l + [l[-1] * 2 ** i for i in range(1, 32)]

def cost(x):
    ans = 0
    for i in range(32):
        if x & (1 << i):
            ans += c[i]
    return ans

ans = cost(m)
for i in range(32):
    if not (m & (1 << i)):
        tmp = m - (m % (1 << i)) + (1 << i)
        ans = min(ans, cost(tmp))

print(ans)

read = lambda: list(map(int, input().split()))
n, L = read()
c = list(read())
for _ in range(5):
    for i in range(n - 2, -1, -1):
        c[i] = min(c[i], c[i + 1])
    for i in range(1, n):
        c[i] = min(c[i], c[i - 1] * 2)
cur = 0
ans = 10 ** 30
L1 = L
for i in range(n - 1, -1, -1):
    cnt = L1 // (2**i)
    cur += cnt * c[i]
    ans = min(ans, cur + c[i])
    L1 -= cnt * (2**i)
ans = min(ans, cur)
for i in range(n - 1, -1, -1):
    if (2**i)>=L:
        ans = min(ans, c[i])
print(ans)


# -*- coding: utf-8 -*-
"""
Created on Mon Jan  8 09:32:18 2018

@author: yanni
"""

n, L = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
size = [2**p for p in range(n)]
for index in range(n):
    if (index > 0):
        c[index] = min(c[index], c[index-1]*2)
for index in range(n):
    if (index > 0):
        temp = n-1-index
        c[temp] = min(c[temp], c[temp+1])
poss = []
base = 0
maxindex = 0
while (size[maxindex] < L and maxindex < n-1):
    maxindex += 1
if (size[maxindex] < L):
    base = (L//size[maxindex]) * c[maxindex]
    L = L % size[maxindex]
if (L == 0):
    print(base)
else:
    poss.append(base + c[maxindex])
    curr = base
    while (L > 0):
        while (size[maxindex] >= 2*L):
            maxindex -= 1
        poss.append(curr + c[maxindex])
        if (maxindex == 0):
            curr += c[0]
            L = 0
        else:
            L -= size[maxindex-1]
            curr += c[maxindex-1]
    poss.append(curr)
    print(min(poss))
    
        


def ii():
    return int(input())
def mi():
    return map(int, input().split())
def li():
    return list(mi())

n, L = mi()
C = li()
for i in range(1, n):
    C[i] = min(C[i], C[i-1] * 2)

x = 2 ** (n-1)
y = 0
z = 10 ** 18
for i in range(n-1, -1, -1):
    t = L // x
    y += C[i] * t
    z = min(z, y + C[i])
    L %= x
    x //= 2
z = min(z, y)
print(z)

#!/usr/bin/env python3

def main():
    n, needed = list(map(int, input().split()))
    costs = list(map(int, input().split()))

    done = False
    while not done:
        done = True
        cur = costs[0]
        for i, x in enumerate(costs[1:], 1):
            cur <<= 1
            if cur < x:
                costs[i] = cur
                done = False
            else:
                cur = x
        for i in range(n - 2, -1, -1):
            if costs[i] > costs[i + 1]:
                costs[i] = costs[i + 1]
                done = False

    def calc(total):
        result = 0
        for i in range(31):
            if total & 1 << i:
                if i < n:
                    result += costs[i]
                else:
                    result += costs[-1] << (i - n + 1)
        return result

    result = calc(needed)
    for i in range(30, -1, -1):
        x = (needed >> i | 0x1) << i
        if x >= needed:
            result = min(result, calc(x))

    print(result)

try:
    while True:
        main()
except EOFError:
    pass


from sys import stdin, stdout


sze = 100
INF = float('inf')

n, l = map(int, stdin.readline().split())
c = list(map(int, stdin.readline().split()))
may = [1 for i in range(sze)]

for i in range(n - 1, -1, -1):
    for j in range(i):
        if c[i] > c[j] * 2 ** (i - j):
            may[i] = 0



ans = INF

cnt = 0
value = 0

for i in range(n - 1, -1, -1):
    if not may[i]:
        continue
    
    v = l - value
    
    if not v % (2 ** i):
        ans = min(ans, cnt + v * c[i] // (2 ** i))
    else:
        ans = min(ans, cnt + (v // (2 ** i) + 1) * c[i])
    
    cnt += v // (2 ** i) * c[i]
    value += (v // (2 ** i)) * (2 ** i)

stdout.write(str(ans))

n, l = map(int, input().split())
p = list(map(int, input().split()))
d = []
d = [[p[i] / 2**i, i + 1] for i in range(n)]
d.sort(key = lambda x: x[0])
res = 10**18
q = l
curres = 0
for i in d:
	if i[1] == 1:
		curres += p[i[1] - 1] * q
		res = min(res, curres)
		break
	curb = q // 2**(i[1] - 1)
	curres += curb * p[i[1] - 1]
	res = min(res, curres + p[i[1] - 1])
	q %= 2**(i[1] - 1)
print(res)

n, l = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(1, len(arr)):
	arr[i] = min(arr[i], arr[i - 1] * 2)
for i in range(64):
	arr.append(arr[-1] * 2)
dp = 0
for i in range(64):
	if ((l >> i) & 1):
		dp += arr[i]
	else:
		dp = min(dp, arr[i])
print(dp)

n, L = list(map(int, input().split()))
pr = list(map(int, input().split()))
res = 0
poss = []
ber = [(pr[i] / 2 ** i, i) for i in range(n)]
ber.sort()
for i in range(n):
    d = L // (2 ** ber[i][1])
    res += d * pr[ber[i][1]]
    L -= d * (2 ** ber[i][1])
    if L == 0:
        poss.append(res)
    poss.append(res + pr[ber[i][1]])
print(min(poss))


n, L = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
for i in range(1, n):
    if (c[i] > c[i-1] * 2):
        c[i] = c[i-1] * 2
ans1 = 0
ans2 = 0
ans = 10**20
for i in range(n-1, -1, -1):
    r1 = L // (2**i)
    r2 = (L + 2**i - 1) // (2**i)
    L -= (r1 * 2**i)
    ans1 = ans2 + r2 * c[i]
    ans2 += r1 * c[i]
    ans = min(ans, ans1)
ans = min(ans, ans2)
print(ans)

n,L=map(int,input().split())

powers=[]
fir=1
for i in range(n):
    powers.append(fir)
    fir*=2
    
c=list(map(int,input().split()))

for i in range(1,n):
    c[i]=min(2*c[i-1],c[i])
cost=0
fincost=[]
#print(powers)
for i in range(n-1,-1,-1):
    cost+=(L//powers[i])*c[i]
    L=L%powers[i]
    if(L==0):
        fincost.append(cost)
        
    else:
        fincost.append(cost+c[i])
print(int(min(fincost)))

def solve(l, costs):
	ans = 0
	for i in range(31, -1, -1):
		if ((l >> i) & 1) == 1:
			ans += min(costs[i + 1], costs[i] + solve(l - ex(2, i), costs))
			break
	return ans

def ex(base, exp):
	ans = 1
	for i in range(exp):
		ans = ans * base
	return ans

n, l = str(input()).split(' ')
n, l = int(n), int(l)

costs = str(input()).split(' ')
costs = [int(c) for c in costs]

for i in range(1, n):
	costs[i] = min(costs[i], 2 * costs[i - 1])
	
for i in range(len(costs), 32):
	costs.append(2 * costs[i - 1])

for i in range(30, -1, -1):
	costs[i] = min(costs[i], costs[i + 1])
	
print(solve(l, costs))



n, L = map(int, input().split())
c = [*map(int, input().split())]
rational = [True] * n
for i in range(n):
	for j in range(n):
		if i < j and c[i] >= c[j]:
			rational[i] = False
		if i < j and c[i] * (2 ** (j - i)) <= c[j]:
			rational[j] = False

def dfs(i, L):
	if i == 0: 
		return L * c[0]
	elif rational[i]:
		Li = 2 ** i
		if Li >= L:
			return min(c[i], dfs(i - 1, L))
		else:
			return (L // Li * c[i]) + dfs(i, L % Li)
	else:
		return dfs(i - 1, L)


print(dfs(n - 1, L))

import sys

n, L = list(map (int, sys.stdin.readline().split()))
c = list (map (int, sys.stdin.readline().split()))
for i in range (1, n):
  c[i] = min (c[i], 2 * c[i-1])
for i in range (n-2, -1, -1):
  c[i] = min (c[i], c[i+1])
#print (c)


res = L // 2 ** (n - 1) * c[n - 1]
L %= 2 ** (n - 1)
tres = 0
for sh in range (n):
  if (L & (2 ** sh)) != 0:
    tres += c[sh]
  else:
    tres = min (tres, c[sh])

res += tres
print (res)


def solve(a1,b1, cur_sum, cur_L, idx):
    if cur_L == 0:
        return cur_sum
    if idx == len(a1)-1:
        if cur_L > 0:
            ost = cur_L%b1[-1] > 0
            if ost:
                cur_sum += a1[-1]
            cur_sum += a1[-1]* (cur_L//b1[-1])
            return cur_sum
        else:
            return cur_sum
    else:
        ost = cur_L%b1[idx] > 0
        if ost:
            s1 = solve(a1,b1, cur_sum+a1[idx]*((cur_L//b[idx]) + 1), 0,idx+1)
            s2 = solve(a1,b1, cur_sum+a1[idx]*((cur_L//b[idx])), cur_L % b1[idx],idx+1)
            return min(s1,s2)
        else:
            return solve(a1,b1, cur_sum+a1[idx]*((cur_L//b[idx])), cur_L % b1[idx],idx+1)
            

            
n, L = list(map(int, input().split()))
a = list(map(int,input().split()))
b = [2**i for i in range(len(a))]
for i in range(len(a)):
        for j in range(len(a) - 1, i, -1):
            if a[j]/b[j] < a[j-1]/b[j-1]:
                a[j], a[j-1] = a[j-1], a[j]
                b[j], b[j-1] = b[j-1], b[j]
ans = solve(a,b,0,L,0)
print (ans)

        


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

c1 = costs[0]
costs = costs[1:]

maincost = lt * c1
mainlen = lt
remcost = 0

currv = 1
for c in costs:
    currv *= 2
    nmainl = lt - (lt % currv)
    prevc = (maincost / mainlen) if maincost != 0 else 0
    if prevc > (c/currv):


        nremlen = mainlen - nmainl
        remcost += (maincost * nremlen // mainlen)

        mainlen = nmainl
        maincost = mainlen * c // currv

    if remcost > c:
        remcost = c
print(maincost + remcost)

n, lit = list(map(int, input().split()))
cost = list(map(int, input().split())) + ([1 << 100] * 33)
n = len(cost)
rlit = lit

for i in range(n):
    for j in range(i-1, -1, -1):
        cost[i] = min(cost[i], cost[j] * (1 << (i - j)))

res = 0

for i in range(n):
    if (1 << i) & lit:
        res += cost[i]

b = []

while lit:
    b.append(lit % 2)
    lit //= 2

rres = res

for i in range(len(b)-1, -1, -1):
    if b[i] == 1:
        for j in range(i-1, -1, -1):
            if b[j] == 0:
                add = cost[j]
                sub = 0
                for k in range(j-1, -1, -1):
                    if b[k] == 1:
                        sub += cost[k]
                res = min(res, rres+add-sub)

for i in range(n):
    if (1 << i) > rlit and cost[i] < res:
        res = cost[i]

print(res)


from itertools import permutations

MOD = 10**9+7

def find_best(c):
    n = 2 ** len(c)
    best_c = c[0] * n
    best_i = 0
    for i, ci in enumerate(c):
        if n // (2**i) * c[i] < best_c:
            best_c = n // (2**i) * c[i]
            best_i = i
    return best_i

def main():
    n, l = [int(c) for c in input().split(' ')]
    c = [int(c) for c in input().split(' ')]
    ans = []
    cur_ans = 0
    while l:
        ind = find_best(c[:n])
        vol = 2**ind
        cnt = l // vol
        l %= vol
        cur_ans += cnt * c[ind]
        ans.append(cur_ans + (l % vol and c[ind] or 0))
        n = ind
    print(min(ans))

while 1:
    main()
    break
# input()


INF = int(1e18)

def read_int():
    return list(map(int, input().split()))


n, l = read_int()
costs = read_int()

bottles = [(1 << i, c) for i, c in enumerate(costs)]
bottles.sort(key=lambda b: (b[1] / b[0], 1 / b[1]))

min_cost = dict()

def find_min_cost(l):
    if l == 0:
        return 0
    if l in min_cost:
        return min_cost[l]
    c = INF
    for b in bottles:
        c1 = (l + b[0] - 1) // b[0] * b[1]
        c2 = l // b[0] * b[1] + find_min_cost(l % b[0]) if l > b[0] else INF
        c = min(c, c1, c2)
    min_cost[l] = c
    return min_cost[l]

print(find_min_cost(l))

n, l = map(int, input().split())
c = list(map(int, input().split()))

v = []
for i in range(n):
    v.append(2**i)
from math import ceil
def sl(n,l,c, bl):
    #print(n, l, c, bl)
    s = []
    for i in range(n):
        if i not in bl:
            s.append((v[i], v[i]/c[i], c[i], i))
    sm = min(s, key=lambda x: -x[1])
    ct = ceil(l / sm[0])
    if sm[0] == 1:
        return ct*sm[2]
    ans = (ct-1)*sm[2]
    ans1 = min(sm[2], sl(n, l-(ct-1)*sm[0], c, bl + [sm[3]]))
    return ans + ans1
print(sl(n, l, c, []))

n,L=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
costPerLemon=[]
ans=12345678901234567890

for i in range(n):
	costPerLemon.append(c[i]/2**i)


size=n
money=0
while size>1:
	target=min(costPerLemon)
	i=costPerLemon.index(target)
	
	times=int(L/(2**i))
	money+=c[i]*times
	L-=(2**i)*times
	
	ans=min(ans,money+c[i])
	size=i
	while len(costPerLemon)>size:
		costPerLemon.pop(-1)
money+=L*c[0]
ans=min(ans,money)

print(ans)



n, L = [int(k) for k in input().split(' ') if k]
dp = [int(k) for k in input().split(' ') if k]
for i in range(1, n):
	dp[i] = min(2 * dp[i - 1], dp[i])
binary = []
while L != 0:
	binary.append(L % 2)
	L //= 2
while len(dp) < len(binary):
	dp.append(2 * dp[-1])
def minify(p):
	result = 999999999999999999999999999
	for i in range(p + 1, len(dp)):
		result = min(result, dp[i])
	if p == 0:
		return min(result, (dp[p] if binary[p] else 0))
	return min(result, (dp[p] if binary[p] else 0) + minify(p - 1))
print(minify(len(binary) - 1))


n, L = list(map(int,input().split()))
arr = [int(x) for x in input().split()]

def pos(x):
    ans = 0
    while(x):
        x //= 2
        ans += 1
    return ans - 1

def solve(ltr):
    if ltr == 0:
        return 0
    val = pos(ltr)
    if val + 1 < n:
        Bmin = min(arr[val + 1:])
    else:
        val = n - 1
        Bmin = 4e20
    minCost = 4e20
    amt = 0
    for i in range(val + 1):
        v = arr[i] / (2 ** i)
        if v <= minCost:
            minCost = v
            amt = i
    minCost = arr[amt]
    minCost *= ltr // (2 ** amt)
    return min(minCost + solve(ltr % ( 2 ** amt)), Bmin)

print(solve(L))