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 itertools import accumulate

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

A=[int(x) for x in input().split()]
dp=[[float('inf') for x in range(N)] for y in range(N)]

#dp[0]=min(A)を捕まえる最短時間を調べる。
m=A.index(min(A))
A=A[m:]+A[:m]

#dp[i][j]=A[j]のスライムをi回魔法を唱えて捕まえるための最小時間。
#dp[0][0]=A[0],dp[0][1]=A[1],dp[0][2]=A[2]...で初期化。
for i in range(N):
  dp[0][i]=A[i]

#dp[1][1]=min(A[1],dp[0][0]),dp[1][2]=min(A[2],dp[0][1])...
#dp[i][j]=min(A[i],dp[i-1][j-1])
#最終的には回数ごとのsum+k*xの最小値が答え。
for i in range(1,N):
  for j in range(N):
    dp[i][j]=min(A[j],dp[i-1][j-1])

dp = [list(accumulate(x)) for x in dp]

ans=float('inf')
for i in range(N):
  ans=min(ans,dp[i][N-1]+i*x)

print(ans)