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
class Segtree(object):
    import math
    def __init__(self, init_val, N, func_type):
        self.func = self.segfunc_min
        self.ide_ele = 10**9 # min
        if func_type == 'max':
            self.func = self.segfunc_max
            self.ide_ele = -10**9 # max
        elif func_type == 'gcd':
            self.func = self.segfunc_gcd
            self.ide_ele = 0 # gcd
        elif func_type == 'lcm':
            self.func = self.segfunc_lcm
            self.ide_ele = 1 # lcm
        elif func_type == 'add':
            self.func = self.segfunc_add
            self.ide_ele = 0 # add

        self.num = 2**(N-1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        self.init_val = init_val

        n = len(self.init_val)
        self.seg[self.num-1:n+self.num-1] = self.init_val[:n]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.func(res,self.seg[p])
            if q&1 == 1:
                res = self.func(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res,self.seg[p])
        else:
            res = self.func(self.func(res,self.seg[p]),self.seg[q])
        return res

    def segfunc_min(self, a, b):
        if a > b:
            return b
        return a

    def segfunc_max(self, a, b):
        if a >= b:
            return a
        return b

    def segfunc_gcd(self, a, b):
        return math.gcd(a,b)

    def segfunc_lcm(self, a, b):
        return a*b//math.gcd(a,b)

    def segfunc_add(self, a, b):
        return a+b
N,x = map(int,input().split())
a = list(map(int,input().split()))
res = 10**18
seg = Segtree(a+a, 2*N, 'min')
# print(seg.seg)
for k in range(N-1,-1,-1):
    tmp = k*x
    tmp += sum([seg.query(N+i-k,N+i+1) for i in range(N)])
    res = min(res,tmp)
print(res)