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.io.*;
import java.util.*;
import java.util.function.Function;


/**
 * Created by Katushka on 11.03.2020.
 */
public class Main {

    public static final Comparator<int[]> COMPARATOR = Comparator.comparingInt(o -> o[0]);

    static Integer[] readArray(int size, InputReader in) {
        Integer[] a = new Integer[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextInt();
        }
        return a;
    }

    static long[] readLongArray(int size, InputReader in) {
        long[] a = new long[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextLong();
        }
        return a;
    }

    static void sortArray(int[] a) {
        Random random = new Random();

        for (int i = 0; i < a.length; i++) {
            int randomPos = random.nextInt(a.length);
            int t = a[i];
            a[i] = a[randomPos];
            a[randomPos] = t;
        }
        Arrays.sort(a);
    }

    public static void main(String[] args) throws FileNotFoundException {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int n = in.nextInt();
        long x = in.nextLong();

        long[] a = readLongArray(n, in);
        long min = Long.MAX_VALUE;
        for (long ai : a) {
            min = Math.min(ai, min);
        }
        List<Integer> mins = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (a[i] <= min + x) {
                mins.add(i);
            }
        }
        if (mins.size() == n) {
            long ans = 0;
            for (long ai : a) {
                ans += ai;
            }
            out.println(ans);
        } else {
            List<Integer> minsDoubled = new ArrayList<>(mins);
            for (int i = 0; i < mins.size(); i++) {
                minsDoubled.add(mins.get(i) + n);
            }

            int maxDist = 0;
            for (int i = 0; i < n; i++) {
                if (a[i] > min + x) {
                    int ind = -Collections.binarySearch(minsDoubled, i + n) - 2;
                    maxDist = Math.max(maxDist, (i - minsDoubled.get(ind) + n) % n);
                }
            }

            long ans = maxDist * x;
            for (int i = 0; i < n; i++) {
                if (a[i] > min) {
                    int ind = Collections.binarySearch(minsDoubled, i + n);
                    if (ind < 0) {
                        ind = -ind - 2;
                    }
                    ind = (ind % mins.size()) + mins.size();
                    long minPossible = Integer.MAX_VALUE;
                    while (ind >= 0 && minsDoubled.get(ind) >= i + n - maxDist) {
                        minPossible = Math.min(minPossible, a[minsDoubled.get(ind) % n]);
                        ind--;
                    }
                    ans += minPossible;
                } else {
                    ans += a[i];
                }
            }
            out.println(ans);

        }
        out.close();
    }


    private static void outputArray(long[] ans, PrintWriter out) {
        StringBuilder str = new StringBuilder();
        for (long an : ans) {
            str.append(an).append(" ");
        }
        out.println(str);
    }

    private static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                createTokenizer();
            }
            return tokenizer.nextToken();
        }

        private void createTokenizer() {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public String nextString() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public char nextChar() {
            return next().charAt(0);
        }

        public int[] nextInts() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                createTokenizer();
            }
            List<Integer> res = new ArrayList<>();
            while (tokenizer.hasMoreElements()) {
                res.add(Integer.parseInt(tokenizer.nextToken()));
            }
            int[] resArray = new int[res.size()];
            for (int i = 0; i < res.size(); i++) {
                resArray[i] = res.get(i);
            }
            return resArray;
        }
    }
}