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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


using namespace std;
using namespace __gnu_pbds;


#define INF (1<<30)
#define F first
#define S second
#define MOD 1000000007
#define mkp(a, b) make_pair(a, b)


typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;


#define FOR(I, A, B) for(int (I) = (A); (I) < (B); (I)++)
#define ROF(I, A, B) for(int (I) = (A); (I) >= (B); (I)--)
#define SQR(A) 1ll*(A)*(A)


typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


const char array_sep[] = " ";
const char array_end[] = "";


const char pair_sep[] = " ";
const char pair_end[] = "";


const char map_sep[] = "->";
const char map_end[] = "\n";


const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int ddx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int ddy[] = {0, 1, 1, 1, 0, -1, -1, -1};


template<typename A> ostream & operator<<(ostream & os, const vector<A> & x)
{
    for(int i = 0; i < x.size(); i++)
        os << x[i] << array_sep;
    os << array_end;
    return os;
}


template<typename A, typename B> ostream & operator<<(ostream & os, const pair<A, B> & x)
{
    os << x.first << pair_sep << x.second << pair_end;
    return os;
}


template<typename A> istream & operator>>(istream & is, vector<A> & x)
{
    for(int i = 0; i < x.size(); i++)
        is >> x[i];
    return is;
}


template<typename A, typename B> istream & operator>>(istream & is, pair<A, B> & x)
{
    is >> x.first >> x.second;
    return is;
}


template<typename _key, typename _val> ostream & operator<<(ostream & os, map<_key, _val> & mp)
{
    for(auto it : mp)   // not for C++98 or earlier
        os << it->F << map_sep << it->S << map_end;
    return os;
}


template<typename _response> void die(_response ans)
{
	cout << ans << endl;
	exit(0);
}

vector<ll> min_cyclic_shift (vector<ll> a) {
	vector<ll> s;
	s.reserve(a.size() << 1);

    for(auto& i: a)
		s.push_back(i);
	for(auto& i: a)
		s.push_back(i);

	int n = (int) s.size();
	int i=0, ans=0;
	while (i < n/2) {
		ans = i;
		int j=i+1, k=i;
		while (j < n && s[k] <= s[j]) {
			if (s[k] < s[j])
				k = i;
			else
				++k;
			++j;
		}
		while (i <= k)  i += j - k;
	}
	vector<ll> res;
	res.reserve(a.size());
    for(int i = ans; i <= ans + n/2 - 1; i++)
		res.push_back(s[i]);
	return res;
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
//	freopen("errlog.log", "w", stderr);
	ios_base::sync_with_stdio(0);
//	cout << fixed << setprecision(3);
//	srand(time(0));

    int n;
    ll x;
    vector<ll> a;

	cin >> n >> x;
	a.resize(n);
	cin >> a;

    vector<ll> r = min_cyclic_shift(a);
    ll ans = r[0];
    for(int i = 1; i < n; i++)
		ans += min(x + r[0], r[i]);
	cout << ans << endl;
	return 0;
}


