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

public class c {
    static long[] cs, has;
    static HashMap<Long, Long>[] memo;

    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        memo = new HashMap[33];
        for (int i = 0; i < 33; i++)
            memo[i] = new HashMap<>();
        int n = in.nextInt();
        long need = in.nextLong();
        cs = new long[31];
        has = new long[31];
        for (int i = 0; i < 31; i++)
            has[i] = 1L << i;
        for (int i = 0; i < n; i++) {
            cs[i] = in.nextLong();
        }
        for (int i = n; i < 31; i++)
            cs[i] = cs[i - 1] * 2;
        for (int i = 0; i < 100; i++) {
            for (int j = 1; j < 31; j++) {
                cs[j] = Math.min(cs[j], 2 * cs[j - 1]);
            }
            for (int j = 31 - 2; j >= 0; j--) {
                cs[j] = Math.min(cs[j], cs[j + 1]);
            }
        }
        
        
        out.println(go(30, need));
        
        
        
        
        out.close();
    }
    
    static long go(int i, long v) {
        if (v <= 0) return 0;
        if (i < 0) return 3000000000000000000L;
        if (memo[i].containsKey(v))
            return memo[i].get(v);
        if (v >= has[i])
            return cs[i] + go(i, v - has[i]);
        long res = cs[i] + go(i, v - has[i]);
        res = Math.min(res, go(i - 1, v));
        memo[i].put(v, res);
        return res;
    }


    static Random rand = new Random();
    static void sort(int[] a) {
        lsbRadixSort(a, true);
    }
    static void sort(long[] a) {
        int n = a.length;
        for (int i = a.length - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            long tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
        Arrays.sort(a);
    }
    static void sort(double[] a) {
        int n = a.length;
        for (int i = a.length - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            double tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
        Arrays.sort(a);
    }
    static void lsbRadixSort(int[] a, boolean signed) {
        int s = 0, n = a.length;
        int[] p = new int[257], b = new int[n];
        int sb = 1 << 31;
        if(signed) for(int i=0;i<n;i++)  a[i] ^= sb;
        while (s < 32) {
            Arrays.fill(p, 0);
            for (int i = 0; i < n; i++)
                p[((a[i] >>> s) & 255)+1]++;
            for(int i=2;i<256;i++)
                p[i] += p[i-1];
            for (int i = 0; i < n; i++)
                b[p[(a[i] >>> s) & 255]++] = a[i];
            int[] tmp = b;  b = a;  a = tmp;
            s += 8;
        }
        if(signed) for(int i=0;i<n;i++)  a[i] ^= sb;
    }
    static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
    static long lcm(long a, long b) { return a / gcd(a, b) * b; }
    static long[] eEuclid(long a, long b) {
        if (b == 0) return new long[] { a, 1, 0 };
        long[] ans = eEuclid(b, a % b);
        long temp = ans[1] - ans[2] * (a / b);
        ans[1] = ans[2];  ans[2] = temp;
        return ans;
    }
    static long modInverse(long a, long m) {
        return ((eEuclid(a, m)[1] % m) + m) % m;
    }
    static class IntList {
        static int[] EMPTY = {};
        int[] a = EMPTY;
        int n = 0;
        void add(int v) {
            if (n >= a.length)
                a = Arrays.copyOf(a, (n << 2) + 8);
            a[n++] = v;
        }
        int get(int idx) {
            return a[idx];
        }
        int size() {
            return n;
        }
    }
    static class DisjointSet {
        int[] s;
	
        public DisjointSet(int n) {
            Arrays.fill(s = new int[n], -1);
        }	
        public int find(int i) {
            return s[i] < 0 ? i : (s[i] = find(s[i]));
        }	
        public boolean union(int a, int b) {
            if ((a = find(a)) == (b = find(b))) return false;
            if(s[a] == s[b]) s[a]--;
            if(s[a] <= s[b]) s[b] = a; else s[a] = b;
            return true;
        }
    }
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        public FastScanner(InputStream i) {
            br = new BufferedReader(new InputStreamReader(i));
            st = new StringTokenizer("");
        }
        public String next() throws IOException {
            if(st.hasMoreTokens())
                return st.nextToken();
            else
                st = new StringTokenizer(br.readLine());
            return next();
        }
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
        public int[] nextOffsetIntArray(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextInt() - 1;
            return arr;
        }
        public int[] nextIntArray(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextInt();
            return arr;
        }
        public int[][] nextIntArray(int n, int m) throws IOException {
            int[][] arr = new int[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    arr[i][j] = nextInt();
            return arr;
        }
        public long[] nextLongArray(int n) throws IOException {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextLong();
            return arr;
        }
        public long[][] nextLongArray(int n, int m) throws IOException {
            long[][] arr = new long[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    arr[i][j] = nextLong();
            return arr;
        }
        public double[] nextDoubleArray(int n) throws IOException {
            double[] arr = new double[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextDouble();
            return arr;
        }
        public double[][] nextDoubleArray(int n, int m) throws IOException {
            double[][] arr = new double[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    arr[i][j] = nextDouble();
            return arr;
        }
        public char[][] nextCharArray(int n, int m) throws IOException {
            char[][] arr = new char[n][];
            for (int i = 0; i < n; i++)
                arr[i] = next().toCharArray();
            return arr;
        }
    }
}
