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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;

public class LemonadeParty {
	public static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
	public static StringTokenizer st;
	public static PrintWriter pw = new PrintWriter(System.out);
	final static boolean debugmode = true;
	public static int k = 7; // for 10^9 + k mods.
	public static long STMOD = 1000000000 + k; // 10^9 + k
	public static void main(String[] args) throws IOException{
		double bestratePer = Double.MAX_VALUE;
		int cups = getInt();
		int req = getInt();
		int req_ = req;
		long [] dp = new long[Math.max(log2(req) + 2,cups)];
		//System.out.println(dp.length);
		long b = Long.MAX_VALUE/3;
		for(int i = 0;i<cups;i++){
			int q = getInt();
			//System.out.println(b + " "+q);
			if (q < b){
				b = q;
			}
			//System.out.println(m +" "+bestratePer);
			dp[i] = b; // can only buy in pwoers of2 
			b*= 2;
		}
		for(int i = cups;i<dp.length;i++){
			dp[i] = 2*dp[i-1];
		}
		long cmin = Long.MAX_VALUE;
		//int cindex = -1;
		long cval = 0;
		long[][] min = new long[dp.length][2];
		for(int i = dp.length-1;i>= 0;i--){
			if (dp[i] < cmin){
				//cindex = i;
				cmin = dp[i];
				cval = getTwoPow(i);
			}
			//min[i][0] = cindex;
			min[i][0] = cmin;
			min[i][1] = cval;
		}
		//System.out.println(Arrays.toString(dp));
		//for(long[] v: min){
		//	System.out.println(Arrays.toString(v));
		//}
		System.out.println(check(req,dp,min));
		/*
		 * 4 4
10000 1000 100 10
		 */
	}
	private static long getTwoPow(int i) {
		if(i == 0){
			return 1;
		}
		else if(i > 2){
			return getTwoPow(i-2)*4;
		}
		return getTwoPow(i-1) * 2;
	}
	private static long check(long req, long[] dp,long[][] min) {
		
		if (req <= 0){
			return 0;
		}
		int pce = log2(req);
		
		long csol =  min[pce][0] + check(req - min[pce][1],dp,min); 
		for(int i = pce+1;i<min.length;i++){
			if(csol > min[i][0]){
				csol = min[i][0];
			}
		}
		return csol;
		/*
		long sol = 0;
			//System.out.println(req + Arrays.toString(min[log2(req)]));
		sol += min[log2(req)][0];
		req -= min[log2(req)][1];
		
		
		return sol + c;
		/*
		 * 5 64
123456789 234567890 345678901 456789012 987654321
		 */
	}
	private static int log2(long req) {
		return (int)( Math.log(req)/Math.log(2));
	}
	public int GCD(int a, int b) {
		   if (b==0) return a;
		   return GCD(b,a%b);
	}
	public static void debug(String toPrint){
		if(!debugmode) {return;}
		pw.println("[DEBUG]: "+toPrint);
	}
	public static void  submit(int[] k){
		pw.println(Arrays.toString(k));
		pw.close();
	}
	public static void submit(int p){
		pw.println(Integer.toString(p));
		pw.close();
	}
	public static void submit(String k){
		pw.println(k);
		pw.close();
	}
	public static void submit(double u){
		pw.println(Double.toString(u));
		pw.close();
	}
	public static void submit(long lng){
		pw.println(Long.toString(lng));
		pw.close();
		
	}
	public static int getInt() throws IOException{
		if (st != null && st.hasMoreTokens()){
			return Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(sc.readLine());
		return Integer.parseInt(st.nextToken());
	}
	public static long getLong() throws IOException{
		if (st != null && st.hasMoreTokens()){
			return Long.parseLong(st.nextToken());
		}
		st = new StringTokenizer(sc.readLine());
		return Long.parseLong(st.nextToken());
	}
	public static double getDouble()throws IOException{
		if (st != null && st.hasMoreTokens()){
			return Double.parseDouble(st.nextToken());
		}
		st = new StringTokenizer(sc.readLine());
		return Double.parseDouble(st.nextToken());
	}
	public static String getString()throws IOException{
		if(st != null && st.hasMoreTokens()){
			return st.nextToken();
		}
		st = new StringTokenizer(sc.readLine());
		return st.nextToken();
	}
	public static String getLine() throws IOException{
		return sc.readLine();
	}
	public static int[][] readMatrix(int lines,int cols) throws IOException{
		int[][] matrr = new int[lines][cols];
		for (int i = 0;i < lines;i++){
			for(int j = 0;j < cols;j++){
				matrr[i][j] = getInt();
			}
		}
		return matrr;
	}
	public static int[] readArray(int lines) throws IOException{
		int[] ar = new int[lines];		
		for (int i = 0;i<lines;i++) ar[i] =getInt();
		return ar;
	}
	
}
