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.
		// Code Author: Shrey Shah
		// Institute : DA-IICT
		// Quote : Think twice , Code Once
		 
		import java.io.*;
		import java.math.BigInteger;
		import java.math.RoundingMode;
		import java.text.DecimalFormat;
		import java.util.*;
		
		
		public class Tester5 {
		
			static double eps=(double)1e-6;
			static long mod=(int)1e9+7;
			static long d,x,y;
			static long  phi[],sumOfGCD[];
			public static void main(String args[]){
				InputReader sc = new InputReader(System.in);
				OutputStream outputStream = System.out;
				PrintWriter out = new PrintWriter(outputStream);
				//---Code Begins Here--------
				int n=sc.nextInt();
				long x=sc.nextLong();
				long b[]=new long[50];
				long c[]=new long[50];
				long temp=x;
				for(int i=0;i<n;i++)
				{
					c[i]=temp;
					b[i]=temp%2;
					temp/=2;
				}
				long m[]=new long[n];
				m[0]=sc.nextLong();
				for(int i=1;i<n;i++)
				{
					m[i]=Math.min(m[i-1]*2,sc.nextLong());
				}
				long min=0,bmin=0;
				min=c[0]*m[0];
				bmin=b[0]*m[0];
				for(int i=1;i<n;i++)
				{
					min=Math.min(min,bmin+c[i]*m[i]);
					min=Math.min(min,(c[i]+1)*m[i]);
					bmin=Math.min(bmin+b[i]*m[i],(b[i]+1)*m[i]);
				}
				out.println(min);
				//---The End-----------------
				out.close();
			}
			private static long cal(int[] a) 
			{
				long max_so_far = Long.MIN_VALUE, max_ending_here = 0,
			    start =0, end = 0, s=0;
					 
				 for (int i=0; i<a.length; i++ )
				 {
					        max_ending_here += a[i];
					 
					        if (max_so_far < max_ending_here)
					        {
					            max_so_far = max_ending_here;
					            start = s;
					            end = i;
					        }
					 
					        if (max_ending_here < 0)
					        {
					            max_ending_here = 0;
					            s = i+1;
					        }
				 }
			return max_so_far;
			}
			private static long fact(long count) {
				long ans=1;
				for(int i=2;i<=count;i++)
					ans*=i;
				return ans;
			}
			static int[] spf(int n)
			{
			    int spf[] = new int[n+1];
			    Arrays.fill(spf,0);
			    spf[1] = 1;
			 
			    for (int i = 2; i <= n; i++)
			    {
			        if (spf[i] == 0)
			        {
			            spf[i] = i;
			            for (int j = 2*i; j <= n; j += i)
			                if (spf[j] == 0)
			                   spf[j] = i;
			            
			        }  
			    }
			    return spf;
			}
			
		    static int[] sieve(int n)
				{
					int prime[] = new int[n+1];
					for(int i=0;i<n;i++)
						prime[i] = 1;
					prime[0]=0;
					prime[1]=0;
					for(int p = 2; p*p <=n; p++)
					{
						// If prime[p] is not changed, then it is a prime
						if(prime[p] == 1)
						{
							// Update all multiples of p
							for(int i = p*2; i <= n; i += p)
								prime[i] = 0;
						}
					
					}
					return prime;
				}
		    
		    
			public static void computeTotient(int n)
			{
			    phi = new long[n+1];
			    for (int i=1; i<=n; i++)
			        phi[i] = i;
			 
			    for (int p=2; p<=n; p++)
			    {
			        // If phi[p] is not computed already,
			        // then number p is prime
			        if (phi[p] == p)
			        {
			            // Phi of a prime number p is
			            // always equal to p-1.
			            phi[p] = p-1;
			 
			            // Update phi values of all
			            // multiples of p
			            for (int i = 2*p; i<=n; i += p)
			            {
			               // Add contribution of p to its
			               // multiple i by multiplying with
			               // (1 - 1/p)
			               phi[i] = (phi[i]/p) * (p-1);
			            }
			        }
			    }
			}
			public static void sumOfGcdPairs(int MAX)
			{
			    computeTotient(MAX);
			    sumOfGCD = new long[MAX];
			    for (int i=1; i<MAX; ++i)
			    {
			        // Iterate throght all the divisors
			        // of i.
			        for (int j=2; i*j<MAX; ++j)
			        	 sumOfGCD[i*j] += i*phi[j];
			    }
			 
			    for (int i=2; i<MAX; i++)
			    	 sumOfGCD[i] +=  sumOfGCD[i-1];
			}
			
			static long modInverse(long A, long M)
			{
				
			    extendedEuclid(A,M);
			    return (x%M+M)%M;    //x may be negative
			}
			static void extendedEuclid(long A, long B) {
			    if(B == 0) {
			        d = A;
			        x = 1;
			        y = 0;
			    }
			    else {
			        extendedEuclid(B, A%B);
			        long temp = x;
			        x = y;
			        y = temp - (A/B)*y;
			    }
			}
	
			static int power(int x,int n)
			{
			    if(n==0)
			        return 1;
			    else if(n%2 == 0)        //n is even
			        return power(x*x,n/2);
			    else                             //n is odd
			        return x*power(x*x,(n-1)/2);
			}
			 static long ce(long x)
				{
					if(x%2!=0)
						return x/2+1;
					return x/2;
				}
			static boolean isSubSequence(String str1, String str2, int m, int n)
			{
			   int j = 0;
			   for (int i=0; i<n&&j<m; i++)
			       if (str1.charAt(j) == str2.charAt(i))
			         j++;
			 
			   return (j==m);
			}
				
			static long fibo(long l) {
		        if (l < 0) {
		            throw new IllegalArgumentException("The fibo value cannot be negative");
		        }
		
		        if (l <= 1) return l;
		
		        long[][] result = {{1, 0}, {0, 1}}; // identity matrix.
		        long[][] fiboM = {{1, 1}, {1, 0}};
		
		        while (l > 0) {
		            if (l%2 == 1) {
		                multMatrix(result, fiboM);
		            }
		            l = l / 2;
		            multMatrix(fiboM, fiboM);
		        }
		
		        return result[1][0];
		    }
		
		    private static void multMatrix(long[][] result, long[][] fiboM) {
		        long a = (result[0][0]%mod * fiboM[0][0]%mod)%mod +  (result[0][1]%mod * fiboM[1][0]%mod)%mod;
		        long b = (result[0][0]%mod * fiboM[0][1]%mod)%mod + ( result[0][1]%mod * fiboM[1][1]%mod)%mod;
		        long c = (result[1][0]%mod * fiboM[0][0]%mod)%mod + ( result[1][1]%mod * fiboM[0][1]%mod)%mod;
		        long d = (result[1][0]%mod * fiboM[0][1]%mod)%mod +  (result[1][1]%mod * fiboM[1][1]%mod)%mod;
		
		        result[0][0] = a;
		        result[0][1] = b;
		        result[1][0] = c;
		        result[1][1] = d;
		    }
		    
		    
			static boolean isPal(String s)
			{
				for(int i=0, j=s.length()-1;i<=j;i++,j--)
				{
					if(s.charAt(i)!=s.charAt(j)) return false;
				}
				return true;
			}
			public static String rev(String s)
			{
				StringBuilder sb=new StringBuilder(s);
				sb.reverse();
				return sb.toString();
			}
			    
			static long lcm(long a, long b)
			{
			    return a * (b / gcd(a, b));
			}
			
			static long gcd(long a, long b)
			{
			    while (b > 0)
			    {
			        long temp = b;
			        b = a % b; // % is remainder
			        a = temp;
			    }
			    return a;
			}
			static long modulo(long a,long b,long c) {
				long x=1;
				long y=a;
				while(b > 0){
					if(b%2 == 1){
						x=(x*y)%c;
					}
					y = (y*y)%c; // squaring the base
					b /= 2;
				}
				return  x%c;
			}
			
			static int mergeSort(int arr[], int array_size)
		    {
		        int temp[] = new int[array_size];
		        return _mergeSort(arr, temp, 0, array_size - 1);
		    }
		      
		    /* An auxiliary recursive method that sorts the input array and
		      returns the number of inversions in the array. */
		    static int _mergeSort(int arr[], int temp[], int left, int right)
		    {
		      int mid, inv_count = 0;
		      if (right > left)
		      {
		        /* Divide the array into two parts and call _mergeSortAndCountInv()
		           for each of the parts */
		        mid = (right + left)/2;
		      
		        /* Inversion count will be sum of inversions in left-part, right-part
		          and number of inversions in merging */
		        inv_count  = _mergeSort(arr, temp, left, mid);
		        inv_count += _mergeSort(arr, temp, mid+1, right);
		      
		        /*Merge the two parts*/
		        inv_count += merge(arr, temp, left, mid+1, right);
		      }
		      return inv_count;
		    }
		      
		    /* This method merges two sorted arrays and returns inversion count in
		       the arrays.*/
		    static int merge(int arr[], int temp[], int left, int mid, int right)
		    {
		      int i, j, k;
		      int inv_count = 0;
		      
		      i = left; /* i is index for left subarray*/
		      j = mid;  /* j is index for right subarray*/
		      k = left; /* k is index for resultant merged subarray*/
		      while ((i <= mid - 1) && (j <= right))
		      {
		        if (arr[i] <= arr[j])
		        {
		          temp[k++] = arr[i++];
		        }
		        else
		        {
		          temp[k++] = arr[j++];
		      
		         /*this is tricky -- see above explanation/diagram for merge()*/
		          inv_count = inv_count + (mid - i);
		        }
		      }
		      
		      /* Copy the remaining elements of left subarray
		       (if there are any) to temp*/
		      while (i <= mid - 1)
		        temp[k++] = arr[i++];
		      
		      /* Copy the remaining elements of right subarray
		       (if there are any) to temp*/
		      while (j <= right)
		        temp[k++] = arr[j++];
		      
		      /*Copy back the merged elements to original array*/
		      for (i=left; i <= right; i++)
		        arr[i] = temp[i];
		      
		      return inv_count;
		    }
			
			
			
			
			public static void debug(Object... o) {
				System.out.println(Arrays.deepToString(o));
			}
			static class Pair implements Comparable<Pair>{
				int x;
				long y;
				Pair(int l,long i){
					x=l;
					y=i;
				}
				@Override
				public int compareTo(Pair o) {
					return Integer.compare(this.x, o.x);
				}
			}
		
			static class InputReader {
				public BufferedReader reader;
				public StringTokenizer tokenizer;
		
				public InputReader(InputStream inputstream) {
					reader = new BufferedReader(new InputStreamReader(inputstream));
					tokenizer = null;
				}
		
				public String nextLine(){
					String fullLine=null;
					while (tokenizer == null || !tokenizer.hasMoreTokens()) {
						try {
							fullLine=reader.readLine();
						} catch (IOException e) {
							throw new RuntimeException(e);
						}
						return fullLine;
					}
					return fullLine;
				}
				public String next() {
					while (tokenizer == null || !tokenizer.hasMoreTokens()) {
						try {
							tokenizer = new StringTokenizer(reader.readLine());
						} catch (IOException e) {
							throw new RuntimeException(e);
						}
					}
					return tokenizer.nextToken();
				}
				public long nextLong() {
					return Long.parseLong(next());
				}
				public int nextInt() {
					return Integer.parseInt(next());
				}
			}
			
		}
	
		