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>
#pragma GCC optimize("O3")
#pragma GCC target("avx")
using namespace std;
const int cm = 1 << 17;
char cn[cm], *ci = cn + cm, ct;
inline char getcha() {
  if (ci - cn == cm) {
    fread_unlocked(cn, 1, cm, stdin);
    ci = cn;
  }
  return *ci++;
}
inline int getint() {
  int A = 0;
  if (ci - cn + 16 > cm)
    while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
  else
    while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
  return A;
}
int main() {
  int N = getint(), X = getint();
  long long kotae = 0;
  int A[2002], B[2001];
  for (int i = 0; i < (N); i++) {
    A[i] = getint();
    kotae += A[i];
    B[i] = 1;
  }
  int dai[2002], shou[2002];
  for (int i = 0; i < (N - 1); i++) dai[i + 1] = i;
  dai[0] = N - 1;
  for (int i = 1; i <= (N - 1); i++) shou[i - 1] = i;
  shou[N - 1] = 0;
  queue<int> P[2], Q[2];
  for (int i = 0; i < (N); i++) {
    int a = i - 1 < 0 ? N - 1 : i - 1;
    int b = i + 1 >= N ? 0 : i + 1;
    if (A[a] < A[i] && A[i] >= A[b]) {
      P[0].push(i);
    }
    if (A[a] > A[i] && A[i] <= A[b]) {
      Q[0].push(i);
    }
  }
  long long kari = kotae;
  for (int i = 0; i < (N); i++) {
    int mae = i & 1;
    int tugi = mae ^ 1;
    while (P[mae].size()) {
      int j = P[mae].front();
      P[mae].pop();
      kari -= A[j];
      if (B[j] >= 2) {
        B[j]--;
        P[tugi].push(j);
      } else {
        B[j] = 0;
        int l = j - 1 < 0 ? N - 1 : j - 1;
        l = shou[l];
        int l2 = l - 1 < 0 ? N - 1 : l - 1;
        int r = j + 1 >= N ? 0 : j + 1;
        r = dai[r];
        int r2 = r + 1 >= N ? 0 : r + 1;
        if (A[l2] < A[r2]) {
          int r3 = r2 + 1 >= N ? 0 : r2 + 1;
          r3 = dai[r3];
          int r4 = r3 + 1 >= N ? 0 : r3 + 1;
          if (A[r2] >= A[r4]) P[tugi].push(r2);
        } else {
          int l3 = l2 - 1 < 0 ? N - 1 : l2 - 1;
          l3 = shou[l3];
          int l4 = l3 - 1 < 0 ? N - 1 : l3 - 1;
          if (A[l4] < A[l2]) P[tugi].push(l2);
        }
        dai[l] = r;
        shou[r] = l;
      }
    }
    while (Q[mae].size()) {
      int j = Q[mae].front();
      Q[mae].pop();
      kari += A[j];
      int l = j - 1 < 0 ? N - 1 : j - 1;
      l = shou[l];
      int l2 = l - 1 < 0 ? N - 1 : l - 1;
      int r = j + 1 >= N ? 0 : j + 1;
      r = dai[r];
      int r2 = r + 1 >= N ? 0 : r + 1;
      if (A[l2] > A[j] && A[j] <= A[r2]) {
        Q[tugi].push(j);
        B[j]++;
      }
    }
    kari += X;
    kotae = min(kotae, kari);
  }
  printf("%lld\n", kotae);
  return 0;
}
