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

public class Codeforces {
	
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(System.out);
	
	static int MOD = 1000000007, prime[];
	static long gcd, x, y;
	static boolean isPrime[];
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long L = sc.nextLong(), bit[] = new long[50], num[] = new long[50];
		long temp_L = L;
		for(int i = 0; i < n; i++) {
			num[i] = temp_L;
			bit[i] = temp_L % 2;
			temp_L /= 2;
		}
		long minGivenBottle[] = new long[n];
		minGivenBottle[0] = sc.nextLong();
		for(int i = 1; i < n; i++)
			minGivenBottle[i] = Math.min(minGivenBottle[i-1]*2, sc.nextLong());
		long min = 0, bits_min = 0;
		min = num[0] * minGivenBottle[0];
		bits_min = bit[0] * minGivenBottle[0];
		for(int i = 1; i < n; i++) {
			min = Math.min(min, bits_min + (num[i] * minGivenBottle[i]));
			min = Math.min(min, (num[i] + 1) * minGivenBottle[i]);
			bits_min = Math.min(bits_min + bit[i] * minGivenBottle[i], (bit[i] + 1) * minGivenBottle[i]);
		}
		System.out.println(min);
	}
	
	static long min_3(long a, long b, long c) {
		if(a < b && a < c)
			return a;
		if(b < c)
			return b;
		return c;
	}
	
	static long max_3(long x, long y, long z) {
		if(x >= y && x >= z)
			return x;
		if(y >= x && y >= z)
			return y;
		return z;
	}
	
	static long power(long x, long y, long m) {
	    if (y == 0)
	        return 1;
	    long p = power(x, y/2, m) % m;
	    p = (p * p) % m;
	    return (y%2 == 0) ? p : (x * p) % m;
	}
	
	public static void prime_sieve(int N) {
        isPrime = new boolean[N+1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for(int i = 2; i*i <= N; i++) {
            if(isPrime[i]==true) {
            	for(int j = 2*i; j <= N; j += i) {
            		isPrime[j] = false;
            		prime[j] = i;
				}
            }
        }
    }
	
	public static long factorial(long num) {
		long result = 1;
		for(int i = 1; i <= num; i++)
			result = result * (long)i;
		return result;
	}
	
	public static void ExtendedEuclidian(long a, long b) {
		if(b == 0) {
	        gcd = a;
	        x = 1;
	        y = 0;
	    }
	    else {
	        ExtendedEuclidian(b, a%b);
	        int temp = (int) x;
	        x = y;
	        y = temp - (a/b)*y;
	    }
	}
	
	public static long GCD(long n, long m) {
		if(m != 0)
			return GCD(m, n % m);
		else
			return n;
	}
	
	static class CustomComp implements Comparator<Object> {
		@Override
        public int compare(Object o1, Object o2) {
			return 1;
        }
	}
	
	static class Graph {
		
	    private int V;
	    private LinkedList<Integer> adj[];
	    boolean visited[];
	    
	    Graph(int v) {
	        V = v + 1;
	        visited = new boolean[V];
	        adj = new LinkedList[V];
	        for(int i = 0; i < V; ++i)
	            adj[i] = new LinkedList<Integer>();
	    }
	 
	    void addEdge(int v, int w) {
	        adj[v].add(w);
	        adj[w].add(v);
	    }
	    
	    // prints BFS traversal from a given source s
	    void BFS(int s) {
	        LinkedList<Integer> queue = new LinkedList<Integer>();
	        visited[s] = true;
	        queue.add(s);
	        while (queue.size() != 0) {
	            s = queue.poll();
	            System.out.print(s+" ");
	            Iterator<Integer> i = adj[s].listIterator();
	            while (i.hasNext()) {
	                int n = i.next();
	                if (!visited[n]) {
	                    visited[n] = true;
	                    queue.add(n);
	                }
	            }
	        }
	    }
	    
	    void DFS(int v, boolean visited[]) {
	        visited[v] = true;
	        System.out.print(v+" ");
	        Iterator<Integer> i = adj[v].listIterator();
	        while (i.hasNext()) {
	            int n = i.next();
	            if (!visited[n])
	                DFS(n, visited);
	        }
	    }
	    
	    boolean isCyclicUndirectedUtil(int v, boolean visited[], int parent) {
	        // Mark the current node as visited
	        visited[v] = true;
	        Integer i;
	 
	        // Recur for all the vertices adjacent to this vertex
	        Iterator<Integer> it = adj[v].iterator();
	        while (it.hasNext()) {
	            i = it.next();
	 
	            // If an adjacent is not visited, then recur for that
	            // adjacent
	            if (!visited[i]) {
	                if (isCyclicUndirectedUtil(i, visited, v))
	                    return true;
	            }
	 
	            // If an adjacent is visited and not parent of current
	            // vertex, then there is a cycle.
	            else if (i != parent)
	                return true;
	        }
	        return false;
	    }
	 
	    // Returns true if the graph contains a cycle, else false.
	    boolean isCyclicUndirected() {
	        // Mark all the vertices as not visited and not part of
	        // recursion stack
	        boolean visited[] = new boolean[V];
	 
	        // Call the recursive helper function to detect cycle in
	        // different DFS trees
	        for (int u = 1; u <= V; u++)
	            if (!visited[u]) // Don't recur for u if already visited
	                if (isCyclicUndirectedUtil(u, visited, -1))
	                    return true;
	 
	        return false;
	    }
	    
	    boolean isCyclicDirectedUtil(int v, boolean visited[], boolean recStack[]) {
	    	if(visited[v] == false) {
	            // Mark the current node as visited and part of recursion stack
	            visited[v] = true;
	            recStack[v] = true;
	     
	            // Recur for all the vertices adjacent to this vertex
	            Iterator<Integer> i = adj[v].listIterator();
	            while(i.hasNext()) {
	            	int n = i.next();
	                if (!visited[n] && isCyclicDirectedUtil(n, visited, recStack))
	                    return true;
	                else if (recStack[n])
	                    return true;
	            }
	        }
	        recStack[v] = false;  // remove the vertex from recursion stack
	        return false;
	    }
	    
	    boolean isCyclicDirected() {
	    	boolean visited[] = new boolean[V];
	    	boolean recStack[] = new boolean[V];
	    	for(int i = 1; i <= V; i++)
	            if (isCyclicDirectedUtil(i, visited, recStack))
	                return true;
	    	return false;
	    }
	    
	    void topologicalSortUtil(int v, boolean visited[], Stack stack) {
			// Mark the current node as visited.
			visited[v] = true;
			
			// Recur for all the vertices adjacent to this vertex
			Iterator<Integer> it = adj[v].iterator();
			while (it.hasNext()) {
				int i = it.next();
				if (!visited[i])
					topologicalSortUtil(i, visited, stack);
			}
			
			// Push current vertex to stack which stores result
			stack.push(new Integer(v));
		}
			
		// The function to do Topological Sort. It uses recursive topologicalSortUtil()
		void topologicalSort() {
			Stack stack = new Stack();
			
			// Mark all the vertices as not visited
			boolean visited[] = new boolean[V];
			
			// Call the recursive helper function to store Topological Sort starting from all
			// vertices one by one
			for (int i = 1; i <= V; i++)
			if (visited[i] == false)
				topologicalSortUtil(i, visited, stack);
			
			// Print contents of stack
			while (stack.empty()==false)
				System.out.print(stack.pop() + " ");
		}
	}
}