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;
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T1, class T2>
ostream& operator<<(ostream& s, pair<T1, T2> P) {
  return s << '<' << P.first << ", " << P.second << '>';
}
template <class T>
ostream& operator<<(ostream& s, vector<T> P) {
  for (int i = 0; i < P.size(); ++i) {
    if (i > 0) {
      s << " ";
    }
    s << P[i];
  }
  return s;
}
template <class T>
ostream& operator<<(ostream& s, vector<vector<T> > P) {
  for (int i = 0; i < P.size(); ++i) {
    s << endl << P[i];
  }
  return s << endl;
}
template <class T1, class T2>
ostream& operator<<(ostream& s, map<T1, T2> P) {
  for (__typeof__((P).begin()) it = (P).begin(); it != (P).end(); ++it) {
    s << "<" << it->first << "->" << it->second << "> ";
  }
  return s << endl;
}
int N;
long long x;
vector<int> vec;
const int MAX_S = 5000;
struct SparseTable {
  static const int LOG_MAX_S = 14;
  int st[LOG_MAX_S][MAX_S * 2];
  int ln[MAX_S];
  void init(const vector<int>& vec) {
    for (int i = 0; i < MAX_S; ++i) {
      st[0][i] = 1 << 30;
      int ti = i, tln = 0;
      while (ti > 0) ti /= 2, ++tln;
      ln[i] = tln - 1;
    }
    for (int i = 0; i < vec.size(); ++i) st[0][i] = vec[i];
    for (int i = 1; i < LOG_MAX_S; ++i) {
      for (int j = 0; j < MAX_S; ++j) {
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
      }
    }
  }
  int get(int a, int b) {
    if (a >= b) return 1 << 30;
    int bet = b - a, row = ln[bet];
    return min(st[row][a], st[row][b - (1 << row)]);
  }
} st;
long long solve() {
  long long res = 1LL << 59;
  st.init(vec);
  for (int con = 0; con < N; ++con) {
    long long tmp = x * con;
    for (int i = 0; i < N; ++i) {
      int Min = 1 << 29;
      if (con <= i)
        chmin(Min, st.get(i - con, i + 1));
      else {
        chmin(Min, st.get(0, i + 1));
        chmin(Min, st.get(N - (con - i), N));
      }
      tmp += Min;
    }
    chmin(res, tmp);
  }
  return res;
}
int main() {
  while (cin >> N >> x) {
    vec.clear();
    for (int i = 0; i < N; ++i) {
      int a;
      cin >> a;
      vec.push_back(a);
    }
    cout << solve() << endl;
  }
}
