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
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static int n;
	static long[] a;
	static long x;
	static HashMap<String,Long> dp = new HashMap<>();

	static long rec(String state) {
		if (dp.containsKey(state)) {
			return dp.get(state);
		}

		long min = Integer.MAX_VALUE;
		int idx = -1;
		for (int i=0; i<n; i++) {
			if (state.charAt(i) == '0' && min > a[i]) {
				min = a[i];
				idx = i;
			}
		}

		if (idx < 0) {
			return 0;
		}

		StringBuilder sb = new StringBuilder(state);
		sb.setCharAt(idx, '1');

		long min2 = Integer.MAX_VALUE;
		int idx2 = -1;
		for (int i=0; i<n; i++) {
			if (state.charAt((i-1+n)%n) == '0' && min2 > a[i]) {
				min2 = a[i];
				idx2 = i;
			}
		}

		StringBuilder sb2 = new StringBuilder(state);
		sb2.insert(0, sb2.charAt(n-1));
		sb2.deleteCharAt(n);
		sb2.setCharAt(idx2, '1');

		long res = Math.min(rec(sb.toString()) + min, rec(sb2.toString()) + min2 + x);
		dp.put(state, res);
		return res;
	}

	static void solve() {
		n = in.nextInt();
		x = in.nextInt();
		a = new long[n];
		StringBuilder sb = new StringBuilder();
		for (int i=0; i<n; i++) {
			a[i] = in.nextInt();
			sb.append("0");
		}
		out.println(rec(sb.toString()));
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		solve();
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}