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
N, X, *A = map(int, open(0).read().split())


class SegmentTree:
    inf = 2 ** 31 - 1
    
    def __init__(self, n):
        """0-indexed."""
        x = 1
        while x < n:
            x *= 2

        self.n = x
        self.dat = [self.inf] * (2 * x - 1)
        
    def update(self, k, v):
        """Update dat[k] to v."""
        k += self.n - 1
        self.dat[k] = v
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])
            
    def query(self, a, b, k=0, l=0, r=0):
        """Returns min in [a, b)."""
        if l >= r:
            r = self.n
            
        if b <= l or r <= a:
            return self.inf
        
        if a <= l and r <= b:
            return self.dat[k]
        
        vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
        return min(vl, vr)


st = SegmentTree(N)
for i, v in enumerate(A):
    st.update(i, v)

ans = 10 ** 10
for k in range(N):
    b = [0] * N
    for i in range(N):
        if i - k < 0:
            b[i] = min(st.query(0, i + 1), st.query(N - (k - i), N))
        else:
            b[i] = st.query(i - k, i + 1)
    ans = min(ans, k * X + sum(b))
print(ans)
