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
from collections import defaultdict
import copy


def solve(dp, collected_slimes, time_taken):
    if all_colour_picked(collected_slimes):
        return
    if dp[collected_slimes] < time_taken:
        return

    for i in range(n):
        if not collected_slimes[i]:
            collected_slimes_copy, new_time_taken = choose_new_slime(collected_slimes, i, time_taken)
            collected_slimes_copy2, new_time_taken2 = perform_magic(collected_slimes, time_taken)
            if new_time_taken < dp[collected_slimes_copy]:
                dp[collected_slimes_copy] = new_time_taken
            if new_time_taken2 < dp[collected_slimes_copy2]:
                dp[collected_slimes_copy2] = new_time_taken2
            solve(dp, collected_slimes_copy, new_time_taken)
            solve(dp, collected_slimes_copy2, new_time_taken2)


def all_colour_picked(collected_slimes):
    return all(item is True for item in collected_slimes)


def choose_new_slime(collected_slimes, num, time_taken):
    collected_slimes_copy = list(copy.deepcopy(collected_slimes))
    collected_slimes_copy[num] = True
    return tuple(collected_slimes_copy), time_taken + a[num]


def perform_magic(collected_slimes, time_taken):
    collected_slimes_copy2 = list(copy.deepcopy(collected_slimes))
    for i in range(n-1):
        collected_slimes_copy2[i] = collected_slimes[i + 1]
    collected_slimes_copy2[n-1] = collected_slimes[0]
    return tuple(collected_slimes_copy2), time_taken + x

if __name__ == '__main__':
    n, x = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    max_value = pow(10, 9) * 2000
    dp = defaultdict(lambda : max_value)
    collected_slimes = tuple([False for x in range(n)])
    solve(dp, collected_slimes, 0)
    for k, v in dp.items():
        if all(item is True for item in k):
            ans = v
    print(ans)
