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.
#include <bits/stdc++.h>
#pragma warning(disable : 4996)
using namespace std;
template <typename T>
T max(T A) {
  return A;
}
template <typename T, typename... args>
T max(T A, T B, args... S) {
  return max(A > B ? A : B, S...);
}
template <typename T>
T min(T A) {
  return A;
}
template <typename T, typename... args>
T min(T A, T B, args... S) {
  return min(A > B ? A : B, S...);
}
template <typename T>
istream &operator>>(istream &in, vector<T> &v) {
  for (auto &x : v) scanf("%d", &x);
  return in;
}
template <typename T>
ostream &operator<<(ostream &in, vector<T> &v) {
  for (auto &x : v) printf("%d ", x);
  return in;
}
long long fast(long long a, long long b, long long pr) {
  if (b == 0) return 1 % pr;
  long long ans = 1 % pr;
  while (b) {
    if (b & 1) {
      ans *= a;
      ans %= pr;
    }
    b >>= 1;
    a *= a;
    a %= pr;
  }
  return ans;
}
int readInt() {
  int n = 0;
  int ch = getchar();
  int sign = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') sign = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
  n = n * sign;
  return n;
}
long long inv_(long long val) {
  return fast(val, static_cast<long long>(1e9 + 7) - 2,
              static_cast<long long>(1e9 + 7));
}
int _builtin_ctz(long long m) {
  int x = 0;
  while ((m & 1) == 0) {
    m >>= 1;
    ++x;
  }
  return x;
}
class solve {
 public:
  solve() {
    long long n = readInt(), L = readInt(), T = L;
    vector<int> v;
    vector<long long> c(n);
    vector<int> idx(n);
    for (int i = 0; i < n; i++) idx[i] = i, c[i] = readInt();
    sort(idx.begin(), idx.end(), [&](const int &a, const int &b) {
      return c[a] * (1 << b) < c[b] * (1 << a);
    });
    long long ans = 0, rem = L, exp = 1e18, A = 1e18;
    for (int i = 0; i < n; i++) {
      ans = ans + (rem / (1 << idx[i])) * c[idx[i]];
      rem = rem % (1 << idx[i]);
      if (rem == 0) {
        A = min(A, ans);
        break;
      }
      A = min(ans + c[idx[i]], A);
    }
    cout << A;
  }
};
int32_t main() {
  int t = 1, i = 1;
  if (0) scanf("%d", &t);
  while (t--) {
    if (0) printf("Case #%d: ", i++);
    new solve;
  }
  return 0;
}
