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 <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

int main(void)
{
    cin.sync_with_stdio(false);
    ll N, x;
    cin >> N >> x;
    vector<ll> As(N);
    REP(n,N) cin >> As[n];
    
    // vector<ll> Bs;
    // auto itr = min_element(ALL(As));
    // auto mn_idx = distance(begin(As), itr);
    // FOR(i,mn_idx,N) {
    //     Bs.pb( As[i] );
    // }
    // REP(i,mn_idx) {
    //     Bs.pb( As[i] );
    // }

    // // for(auto b: Bs) cout << b << ",";
    // // cout << endl;

    // As = Bs;

    vector<ll> costs = Bs;
    ll ans = 1e15;
    REP(k,N) { // 鬲疲ｳ輔ｒ蜚ｱ縺医ｋ蝗樊焚
        vector<ll> new_costs(N);
        REP(n,N) {
            new_costs[n] = min(costs[n], costs[(n - k + N) % N]);
        }
        costs = new_costs;
        ans = min(ans, accumulate(ALL(costs), 0LL) + k * x);
    }
    cout << ans << endl;

    // ll longest_streak = 0;
    // ll ans = As[0];
    // FOR(n,1,N) {
    //     ll cost = As[n];
    //     for(int n2 = n-1; n2 >= 0; --n2) {
    //         ll diff = n - n2;
    //         ll cost2 = diff * x;
    //         if (cost2 < cost) {
    //             longest_streak = max(longest_streak, diff);
    //             cost = As[n2];
    //         }
    //     }
    //     ans += cost;
    // }
    // ans += longest_streak * x;
    
    // cout << ans << endl;
    return 0;
}
