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

/**
  * Built using my Brain
  * Actual solution is at the bottom
  *
  * @author Lenard Hoffstader
*/

public class cfjava
{
  public static void main(String[] args)
  {
    OutputStream outputStream = System.out;
    FastReader in = new FastReader();
    PrintWriter out = new PrintWriter(outputStream);
    PROBLEM solver = new PROBLEM();
    int t=1;
    // t=in.nextInt();
    for(int i=0;i<t;i++){
      solver.solve(in, out);
    }
    out.close();
  }

  static class PROBLEM
  {
    long money[];
    public void solve(FastReader in,PrintWriter out)
    {
      int n=in.nextInt();
      long ltrs=in.nextLong();
      money=new long[32];
      Arrays.fill(money,Long.MAX_VALUE);
      long x=0;
      long one=1;
      for(int i=0;i<n;i++){
        x=in.nextLong();
        for(int j=i;j<32;j++){
          money[j]=Math.min(money[j],x*((one<<j)/(one<<i)));
        }
      }
      long ans=Long.MAX_VALUE;
      while(true){
        ans=Math.min(ans,getVal(ltrs,one));
        ltrs=getNext(ltrs,one);
        if(ltrs==-1)break;
      }
      out.println(ans);
    }
    long getNext(long n,long one){
      long x=0,val=0;
      for(int i=0;i<32;i++){
        x=(one<<i);
        if((n&x)>0){x=i;break;}
      }
      if(x==31)return -1;
      for(int i=(int)x;i<32;i++){
        val=(one<<i);
        if((n&val)>0){
          val=~val;
          n&=val;
        }
        else {
          n|=val;
          break;
        }
      }
      return n;
    }
    long getVal(long n,long one){
      long x=0,ans=0;
      for(int i=0;i<32;i++){
        x=(one<<i);
        if((x&n)>0)ans+=money[i];
      }
      return ans;
    }
  }
  
  static class FastReader 
  {
    BufferedReader br; 
    StringTokenizer st;

    public FastReader() 
    { 
      br = new BufferedReader(new InputStreamReader(System.in)); 
    } 

    String next() 
    { 
      while (st == null || !st.hasMoreElements()) 
      {
        try
        { 
          st = new StringTokenizer(br.readLine()); 
        } 
        catch (IOException  e) 
        { 
          e.printStackTrace(); 
        } 
      } 
      return st.nextToken(); 
    } 

    int nextInt(){return Integer.parseInt(next());}

    long nextLong(){return Long.parseLong(next());} 

    double nextDouble(){return Double.parseDouble(next());}

    boolean nextBoolean(){
      if(nextInt()==1)return true;
      else return false;
    }
    // boolean nextBoolean(){return Boolean.parseBoolean(next());}

    String nextLine() 
    { 
      String str = ""; 
      try
      { 
        str = br.readLine(); 
      } 
      catch (IOException e){e.printStackTrace();} 
      return str; 
    } 
  }
}
