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.*;

public class C {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int n = sc.nextInt();
		int l = sc.nextInt();
		long[] arr = new long[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}

		long[] best = new long[n];
		best[0] = arr[0];
		for (int i = 1; i < n; i++)
			best[i] = Math.min(best[i - 1] * 2, arr[i]);

		long[] good = new long[n];
		good[n - 1] = best[n - 1];
		for (int i = n - 2; i >= 0; i--) {
			good[i] = Math.min(best[i], good[i + 1]);
		}
		// System.out.println(l);
		// int myIdx = Integer.highestOneBit(l);
		// int upper = 0;
		// for (int i = 0; i <= 31; i++)
		// if ((myIdx & (1 << i)) != 0) {
		// upper = i;
		// }
		// if (Integer.bitCount(l) == 1 && upper < n) {
		// pw.println(good[upper]);
		// pw.flush();
		// return;
		// }
		long[] pow2 = new long[n];
		long ans = 1;
		pow2[0] = 1;
		for (int i = 1; i < n; i++) {
			ans *= 2;
			pow2[i] = ans;
		}
		long res = Long.MAX_VALUE;

		for (int i = n - 1; i >= 0; i--) {
			if (pow2[i] >= l) {
				res = Math.min(res, good[i]);
			}
		}
		long now = 0;
		for (int i = n - 1; i >= 0; i--) {
			if (l <= 0)
				break;
			if (pow2[i] <= l) {
				long cnt = (l / pow2[i]);
				l -= 1l * (cnt) * pow2[i];
				now += 1l * cnt * good[i];
			}
			long min = Long.MAX_VALUE;
			for (int j = i; j >= 0; j--) {
				if (pow2[j] >= l)
					if (sum(l, good) >= good[j]) {
						min = Math.min(min, good[j]);
					}
			}
			if (min != Long.MAX_VALUE) {
				// now += min;
//				l = 0;
				res = Math.min(now + min, res);
				// break;
			}

		}
		pw.println(Math.min(res, now));
		pw.flush();
	}

	static long sum(int l, long[] arr) {
		long ret = 0;
		for (int i = arr.length - 1; i >= 0; i--) {
			if (((1 << i) & l) != 0)
				ret += arr[i];
		}
		return ret;
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

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

		public boolean ready() throws IOException {
			return br.ready();
		}
	}
}
