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 = map(int,input().split())
a = list(map(int,input().split()))

inf = float('inf')
ans = inf

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [inf for _ in range(2*self.N)]
    
    def update(self, k, x):
        k += self.N-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = min([self.data[2*k+1], self.data[2*k+2]])
            
    
    # [l,r)
    def query(self, l, r):
        L = l + self.N
        R = r + self.N
        s = inf
        while L < R:
            if R & 1:
                R -= 1
                s = min([s, self.data[R-1]])
            
            if L & 1:
                s = min([s, self. data[L-1]])
                L += 1
            L >>= 1; R >>= 1
        return s

st = SegmentTree(N)
for i, ai in enumerate(a):
    st.update(i, ai)

def time(i, k):
    if i+k+1 <= N:
        tmp = st.query(i, i+k+1)
    else:
        tmp = min(st.query(0, (i+k) % N + 1), st.query(i, N))
    return tmp

# k回魔法を唱える
for k in range(N):
    res = k*x
    for i in range(N):
        res += time(i, k)
    ans = min(ans, res)

print(ans)