Home

Problem Statement

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$

Sample Input 1

2 10
1 100

Sample Output 1

12

Snuke can act as follows:

• Catch a slime in color $1$. This takes $1$ second.
• Cast the spell. The color of the slime changes: $1$ → $2$. This takes $10$ seconds.
• Catch a slime in color $1$. This takes $1$ second.

Sample Input 2

3 10
100 1 100

Sample Output 2

23

Snuke can act as follows:

• Catch a slime in color $2$. This takes $1$ second.
• Cast the spell. The color of the slime changes: $2$ → $3$. This takes $10$ seconds.
• Catch a slime in color $2$. This takes $1$ second.
• Cast the soell. The color of each slime changes: $3$ → $1$, $2$ → $3$. This takes $10$ seconds.
• Catch a slime in color $2$. This takes $1$ second.

Sample Input 3

4 10
1 2 3 4

Sample Output 3

10

Snuke can act as follows:

• Catch a slime in color $1$. This takes $1$ second.
• Catch a slime in color $2$. This takes $2$ seconds.
• Catch a slime in color $3$. This takes $3$ seconds.
• Catch a slime in color $4$. This takes $4$ seconds.