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 <cstdio>
#include <vector>
#include <algorithm>
#include <stdint.h>

int64_t prev[100000];
int64_t next[100000];
int64_t as[100000];
int64_t bs[100000];
int64_t slope[100000];
int64_t total_slope;
int64_t t;

std::vector<int64_t> vanish[100001];

void calc_slope(int64_t x){
  bs[x]+=t*slope[x];
  total_slope-=slope[x]*as[x];
  slope[x]=(as[next[x]]>as[x])-(as[x]>as[prev[x]]);
  bs[x]-=t*slope[x];
  total_slope+=slope[x]*as[x];
  if(slope[x]<0){
    //printf("VVV %ld %ld\n",bs[x],x);
    vanish[bs[x]].push_back(x);
  }
}

int main(){
  int64_t N,X;
  scanf("%ld %ld",&N,&X);
  for(int64_t i=0;i<N;i++){
    scanf("%ld",&as[i]);
  }
  prev[0]=N-1;
  std::iota(prev+1,prev+N,0);
  next[N-1]=0;
  std::iota(next,next+N-1,1);
  int64_t sum=0;
  total_slope=X;
  std::fill(bs,bs+N,1);
  for(int64_t i=0;i<N;i++){
    calc_slope(i);
    sum+=as[i];
    //printf("as[%ld]=%ld\n",i,as[i]);
  }
  int64_t best=sum;
  //printf("SUM[0]=%ld\n",sum);
  for(t=1;t<=N;t++){
    sum+=total_slope;
    //printf("SUM+=%ld\n",total_slope);
    //printf("SUM[%ld]=%ld\n",t,sum);
    for(int64_t a:vanish[t]){
      //printf("VANISH %ld\n",a);
      total_slope-=slope[a]*as[a];
      prev[next[a]]=prev[a];
      next[prev[a]]=next[a];
      calc_slope(prev[a]);
      calc_slope(next[a]);
    }
    best=std::min(best,sum);
    for(int64_t i=0;i<N;i++){
      //printf("as[%ld]=%ld\n",i,as[i]);
      //printf("bs[%ld]=%ld\n",i,bs[i]);
      //printf("slope[%ld]=%ld\n",i,slope[i]);
    }
  }
  printf("%ld\n",best);
  return 0;
}
