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
# define _CRT_SECURE_NO_WARNINGS 1
# define _USE_MATH_DEFINES
# include <iostream>
# include <numeric>
# include <string>
# include <bitset>
# include <vector>
# include <algorithm>
# include <cstdlib>
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iomanip>
# include <queue>
# include <sstream>
# include <unordered_set>
# include <unordered_map>
# include <climits>
# include <complex>
# include <cmath>
# include <list>
# include <functional>
# include <string>
# include <ctime>
# include <set>
# include <forward_list>
# include <map>
# include <stack>
using namespace std;
# define INF ((int)(1<<25))
# define REP(i,n) for(int i=0;i<(int)n;i++)
# define FOR(i,n) REP(i,n)
# define FORI(i,k,n) for(int i=k;i<(int)n;i++)
# define TORAD 2.0*M_PI/360.0
# define INT(x) int x;cin>>x;
# define STRING(x) string x;cin>>x;
# define STR(x) STRING(x);
# define DOUBLE(x) double x;cin>>x;
# define DBL(x) DOUBLE(x); 
# define ALL(x) begin(x),end(x)
# define RALL(x) (x).rbegin(),(x).rend()
# define DEBUG(x) cout<<#x<<":"<<x<<endl;
# define EPS 1e-12
#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#endif
typedef long long lint;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<int> vi;
typedef vector<lint> vl;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
const int dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 };
const int M = 1000000007;
template<class T> void debug(T a) { for ( auto i : a )cout << i << endl; }

#define int lint

int main()
{
	int n, x;
	cin >> n >> x;
	vi a, X;

	FOR(i, n)
	{
		INT(k);
		a.push_back(k);
		X.push_back(0);
	}
	lint ans = 0;
	int p = 0;
	auto prev = [n] (int i)->int
	{
		return (i == 0 ? n - 1 : i - 1);
	};
	auto next = [n] (int i)->int
	{
		return (i == n - 1 ? 0 : i + 1);
	};
	FOR(j, 2)FOR(i, n)
	{
		int pr = prev(i);
		if ( a[i] > a[pr] + x )
		{
			a[i] = a[pr] + x;
			X[i] = X[pr] + 1;
			p = max(p, X[i]);
		}
	}
	ans += p*x;
	bool ok = false;
	FOR(i, n)
	{
		if ( ok )break;
		if ( X[i] == 0 )
		{
			int c = 1, j= i;
			while ( 1 )
			{
				if ( X[next(j)] == 0 )break;
				if ( next(j) == 0 )ok = true;
				j = next(j);
				c++;
			}
			ans += c*a[i];
			i = j;
		}
	}
	cout << ans << endl;
}