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.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Queue;

public class A3 {

	static long compute(long[] minCost, long[] cap, long L, int check) {
		long ans = 0;
		int j = Arrays.binarySearch(cap, L);
		if (j < 0) {
			j = Math.abs(j + 1);
			if(check == 1){
				j--;
			}
		}
		while (j >= 0 && L > 0) {
			if (cap[j] > L) {
				long temp1 = compute(minCost, cap, cap[j], 0);
				long temp2 = compute(minCost, cap, L, 1);
				if (temp1 < temp2) {
					ans += temp1;
					return ans;
				} else {
					j--;
				}
			}
			ans += minCost[j];
			L -= cap[j];
			j = Arrays.binarySearch(cap, L);
			if (j < 0) {
				j = Math.abs(j + 1);
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		OutputWriter out = new OutputWriter(System.out);
		int n = in.readInt();
		int L = in.readInt();
		long arr[] = new long[n];
		long cap[] = new long[31];
		long minCost[] = new long[31];
		Arrays.fill(minCost, Long.MAX_VALUE);
		int j = 0;
		cap[0] = 1;
		while (j < n) {
			int x = in.readInt();
			arr[j] = x;
			j++;
		}
		j = 1;
		while (j < 31) {
			cap[j] = 2 * cap[j - 1];
			j++;
		}
		j = 0;
		minCost[0] = arr[0];
		while (j < 31) {
			int i = 0;
			long c = cap[j];
			while (i < n) {
				long req = (long) (arr[i] * Math.ceil(((cap[j] * 1.0) / cap[i])));
				minCost[j] = Math.min(minCost[j], req);
				i++;
			}
			if (j != 0)
				minCost[j] = Math.min(minCost[j], 2 * minCost[j - 1]);
			j++;
		}
		// for (int i = 0; i < 31; i++)
		// System.out.print(minCost[i] + " ");
		j = Arrays.binarySearch(cap, L);
		int temp = 0;
		if (j < 0) {
			j = Math.abs(j + 1);
		}
		long ans = 0;
//		while (j >= 0 && L > 0) {
//			long temp1 = compute(minCost, cap, cap[j]);
//			long temp2 = compute(minCost, cap, L);
//			if (cap[j] > L) {
//				if (temp1 < temp2) {
//					ans += temp1;
//					break;
//				}
//			}
//			ans += minCost[j];
//			L -= cap[j];
//			j = Arrays.binarySearch(cap, L);
//			// System.out.println(j);
//			// if (j < 0) {
//			// j = Math.abs(j + 1);
//			// }
//		}
		System.out.println(compute(minCost, cap, L,0));
		out.close();
	}

	private static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public long readLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			long sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int readInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public String readString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuffer res = new StringBuffer();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		static boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public String next() {
			return readString();
		}
	}

	private static class OutputWriter {
		private final PrintWriter writer;

		public OutputWriter(OutputStream outputStream) {
			writer = new PrintWriter(outputStream);
		}

		public OutputWriter(Writer writer) {
			this.writer = new PrintWriter(writer);
		}

		public void print(Object... objects) {
			for (int i = 0; i < objects.length; i++) {
				if (i != 0)
					writer.print(' ');
				writer.print(objects[i]);
			}
		}

		public void printLine(Object... objects) {
			print(objects);
			writer.println();
		}

		public void close() {
			writer.close();
		}
	}
}