Snuke lives in another world, where slimes are real creatures and kept by some people. Slimes come in N colors. Those colors are conveniently numbered 1 through N. Snuke currently has no slime. His objective is to have slimes of all the colors together.

Snuke can perform the following two actions:

* Select a color i (1≤i≤N), such that he does not currently have a slime in color i, and catch a slime in color i. This action takes him a_i seconds.

* Cast a spell, which changes the color of all the slimes that he currently has. The color of a slime in color i (1≤i≤N-1) will become color i+1, and the color of a slime in color N will become color 1. This action takes him x seconds.




Find the minimum time that Snuke needs to have slimes in all N colors.

Constraints

* 2≤N≤2,000
* a_i are integers.
* 1≤a_i≤10^9
* x is an integer.
* 1≤x≤10^9

Input

The input is given from Standard Input in the following format:


N x
a_1 a_2 ... a_N


Output

Find the minimum time that Snuke needs to have slimes in all N colors.

Examples

Input

2 10
1 100


Output

12


Input

3 10
100 1 100


Output

23


Input

4 10
1 2 3 4


Output

10
#include <bits/stdc++.h>
using namespace std;
using str = string;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vec<vec<T>>;
template <class T>
using que = queue<T>;
template <class T>
using pque = priority_queue<T>;
template <class... T>
using tup = tuple<T...>;
using vint = vec<long long>;
using vvint = vvec<long long>;
using vstr = vec<str>;
using pint = pair<long long, long long>;
using vp = vec<pint>;
using tll = tup<long long, long long, long long>;
using vt = vec<tll>;
using mint = map<long long, long long>;
using dict = map<str, long long>;
using qint = que<long long>;
using qp = que<pint>;
using pqint = pque<long long>;
using pqp = pque<pint>;
const long long INF = LLONG_MAX - INT_MAX, MOD = 1e9 + 7, LIMIT = 100001;
const long long dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
const long double EPS = 1e-9;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long factorial(long long a) { return a < 2 ? 1 : factorial(a - 1) * a; }
long long summation(long long a) { return a < 1 ? 0 : (a * a + a) / 2; }
long long combination(long long n, long long r) {
  long long res = 1;
  for (long long i = (long long)(1); i < (long long)(r + 1); i++)
    res *= n--, res /= i;
  return res;
}
const str alphabet = "abcdefghijklmnopqrstuvwxyz";
long long a, b, c, k, n, m, x, y, z, w, h, res = 0, cnt = 0, sum = 0, mx = -INF,
                                           mn = INF;
str s, t;
bool flag = true;
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cin >> n >> x;
  long long time[n];
  for (long long i = (long long)(0); i < (long long)(n); i++) {
    cin >> time[i];
  }
  for (long long i = (long long)(0); i < (long long)(n); i++) {
    cnt = INF;
    for (long long j = (long long)(0); j < (long long)(n); j++) {
      long long tmp;
      if (i - j < 0) {
        tmp = i - j + n;
      } else {
        tmp = i - j;
      }
      cnt = min(cnt, time[tmp] + j * x);
    }
    mx = max(mx, cnt);
    res += cnt % 10;
  }
  cout << (res + mx / 10 * 10), cout << '\n';
}
