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 sys
input = sys.stdin.buffer.readline

class segtree:

    def __init__(self, n, operator, identity):
        """
        n:データ配列のサイズ
        operator:演算子(モノイド)。関数オブジェクト 最小=min, 最大=max
        identity:演算子に対応する単位元
        """
        nb = bin(n)[2:] #２進数に変換して先頭の0bを取り除く
        bc = sum([int(digit) for digit in nb]) #bitで1が立ってる数。これが1のときはちょうど2^nb.そうじゃないときは、2^nb<n<2^(nb+1)
        if bc == 1: #2^nbなら
            self.num_end_leaves = 2**(len(nb)-1) #最下段の葉っぱは2^nb個
        else:#そうじゃないなら2^(nb+1)確保
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)] #単位元で初期化

        self.identity = identity 
        self.operator = operator
        #後で使うので単位元と演算子を持っておく

    def update(self,x,val):
        """
        x:代入場所
        val:代入する値
        """
        actual_x = x+self.num_end_leaves #1-indexの末端の葉のindexがどこから始まるか分を足す(例えばデータ配列サイズ4のとき木配列サイズは8で、後半部はindex4から始まる。
        self.array[actual_x] = val #値を更新する
        while actual_x > 0 :
            actual_x = actual_x//2#親を見る
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])#あたらしい子をつかって親を更新

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        """
        q_left：クエリ区間の左
        q_right:クエリ区間の右
        arr_ind:木配列のインデックス。最初は親なので1
        leaf_left:木配列インデックスに対して、それが表す葉がカバーする範囲の左
        depth:木配列での深さ。カバー範囲の広さの計算に使用
        """
        width_of_floor = self.num_end_leaves//(2**depth) #今の葉のカバー幅
        leaf_right = leaf_left+width_of_floor-1 #左端とカバー幅から今の葉のカバー範囲の右を求める。

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity #クエリ領域と葉が関係ないなら単位元を返す

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind] #クエリ領域に葉がすっぽり入ってるなら、葉の値を返す

        else: #そうじゃないならば、子を見る
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)#子の左
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)#子の右
            return self.operator(val_l,val_r)#子をマージする演算をする。

N, x = map(int,input().split())

s_tree = segtree(N*2,min,float("inf")) #N⇒1になるので二倍の配列を準備
arr = list(map(int,input().split()))

for i in range(N):
    s_tree.update(i, arr[i])
    s_tree.update(i+N, arr[i])

ans = float("inf")
for i in range(N):#i = 魔法をかける回数
    tmp = i * x
    for k in range(N,2*N):#i回魔法をかけてスライムkに変更できうる区間の中で、最小コストのスライムを選ぶ 
        tmp += s_tree.get(k-i,k)
    ans = min(ans,tmp) #合計コストが答のものが答
    
print(ans)