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 java.util.*;
import java.io.*;

public class Solution
{
       static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                                 BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
    static int parent(int x , int p[])
    {
           if(p[x] == x)
           return x;
           
           return (p[x] = parent(p[x],p));
    }
    
    static void union(int a , int b , int p[] , int size[])
    {
           a = parent(a,p);
           b = parent(b,p);
           
           if(size[a] < size[b])
           {
                  int temp = a;
                  a = b;
                  b = temp;
           }
           p[b] = a;
           size[a] += size[b];
    }
    
   
  
  static int max(int x)
  {
         for(int j = 30 ; j >= 0 ; j--)
         {
                if((x&(1<<j)) > 0)
                return j;
         }
         return -1;
  }
  static void dfs(int n , LinkedList<Integer> arr[] , int p , int pp[])
  {
         pp[n] = p;
         for(Integer i : arr[n])
         {
                if(i != p)
                {
                       dfs(i,arr,n,pp);
                }
         }
  }
  
  static void dfs2(int n , LinkedList<Integer> arr[] , int p , int w[] , long dp[] , long max[])
  {
         long mx = 0;
         for(Integer i : arr[n])
         {
                if(i != p)
                {
                       dfs2(i,arr,n,w,dp,max);
                       dp[n] += dp[i]+2*w[i];
                       mx = Math.max(mx,w[i]+max[i]);   
                }
         }
         max[n] = mx;
  }
  
 static int getSum( int index , int BITree[])
{
    int sum = 0; // Iniialize result
  
    // index in BITree[] is 1 more than the index in arr[]
   // index = index + 1;
  
    // Traverse ancestors of BITree[index]
    while (index>0)
    {
        // Add current element of BITree to sum
        sum += BITree[index];
  
        // Move index to parent node in getSum View
        index -= index & (-index);
    }
    return sum;
}
  
// Updates a node in Binary Index Tree (BITree) at given index
// in BITree. The given value 'val' is added to BITree[i] and 
// all of its ancestors in tree.
static void updateBIT(int n, int index, int val , int BITree[])
{
    // index in BITree[] is 1 more than the index in arr[]
    //index = index + 1;
  
    // Traverse all ancestors and add 'val'
    while (index <= n)
    {
    // Add 'val' to current node of BI Tree
    BITree[index] += val;
  
    // Update index to that of parent in update View
    index += index & (-index);
    }
}
static int max;
static long inv(int arr[])
{
       int n = arr.length;
       int bit[]  = new int[n+1];
       long ans = 0;
       for(int i = 0 ; i < n; i++)
       {
              updateBIT(n,arr[i],1,bit);
              ans += getSum(n,bit)-getSum(arr[i],bit);
       }
       return ans;
}


static void dfs(int n , int arr[] , LinkedList<Integer> g[] , HashMap<Integer,Integer> map[] , int prime[] , int p)
{
      HashMap<Integer,Integer> mx = new HashMap<Integer,Integer>(); 
       HashMap<Integer,Integer> nextmx = new HashMap<Integer,Integer>(); 
       
       int temp = arr[n];
       for(Integer i : g[n])
       {
              if(i != p)
              {
                     dfs(i,arr,g,map,prime,n);
                     for(Map.Entry entry : map[i].entrySet())
                     {
                            int k = (int)entry.getKey();
                            int v = (int)entry.getValue();
                            
                            if(arr[n]%k == 0)
                            {
                            if(!mx.containsKey(k))
                            mx.put(k,v);
                            
                            else if(!nextmx.containsKey(k))
                            {
                                 if(v >= mx.get(k))
                                 {
                                         nextmx.put(k,mx.get(k));
                                          mx.put(k,v);
                                 }
                                 
                                 else
                                 {
                                        nextmx.put(k,v);
                                 }
                            }
                            
                            
                            else
                            {
                                   if(v >= mx.get(k))
                                   {
                                          nextmx.put(k,mx.get(k));
                                          mx.put(k,v);
                                   }
                                   
                                   else if(v >= nextmx.get(k))
                                   nextmx.put(k,v);
                            }
                     }
              }
       }
}

while(temp > 1)
{
       int x = prime[temp];
       while(temp%x == 0)
       {
              temp = temp/x;
       }
      // int curr = 0;
       if(mx.containsKey(x))
       {
              max = Math.max(max,mx.get(x)+1);
              
              if(nextmx.containsKey(x))
              max = Math.max(max,mx.get(x)+nextmx.get(x)+1);
              
              map[n].put(x,mx.get(x)+1);
       }
       
       else
       {
       map[n].put(x,1);
       max = Math.max(max,1);
       }
}

}
       public static void main(String []args) throws IOException
       {
              Reader sc = new Reader();
              int n = sc.nextInt();
              int l = sc.nextInt();
              int arr[] = new int[31];
              for(int i = 0 ; i < n ; i++)
              {
                     arr[i] = sc.nextInt();
                     
              }
              long sum = 0;
              long ans = Long.MAX_VALUE;
              for(int i = 30 ; i >= 0 ; i--)
              {
                     if((l&(1<<i)) > 0)
                     {
                        long min = Long.MAX_VALUE;
                        for(int j = 0 ; j <= i ; j++)
                        {
                               if(arr[j] > 0)
                               min = Math.min(min,(long)Math.pow(2,i-j)*(long)arr[j]);
                        }
                        sum += min;
                     }
                     
                     else
                     {
                        long min = Long.MAX_VALUE;
                        for(int j = 0 ; j <= i ; j++)
                        {
                               if(arr[j] > 0)
                               min = Math.min(min,(long)Math.pow(2,i-j)*(long)arr[j]);
                        }
                        ans = Math.min(ans,sum+min);
                     }
              }
              ans = Math.min(ans,sum);
              System.out.println(ans);
       }
}