/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
高橋君は異世界に住んでいます。 この世界には N 色のスライムがいます。 最初、高橋君はどの色のスライムも飼っていません。 高橋君の目標は、全色のスライムを一緒に飼うことです。
高橋君は次の 2 種類の操作を行えます。
- 今飼っていないスライムの色 i (1≤i≤N) をひとつ選ぶ。 色 i のスライムを捕まえて飼う。 この操作には a_i 秒掛かる。
- 魔法を唱える。 すると、今飼っている各スライムについて、色 i (1≤i≤N-1) のスライムは色 i+1 へ変色する。 ただし、色 N のスライムは色 1 へ変色する。 この操作には x 秒掛かる。
高橋君が全色のスライムを一緒に飼うためには、最短で合計何秒掛かるかを求めてください。
制約
- 2≤N≤2,000
- a_i は整数である。
- 1≤a_i≤10^9
- x は整数である。
- 1≤x≤10^9
入力
入力は以下の形式で標準入力から与えられる。
N x a_1 a_2 ... a_N
出力
高橋君が全色のスライムを一緒に飼うためには、最短で合計何秒掛かるかを出力せよ。
入力例 1
2 10 1 100
出力例 1
12
次のように操作を行えばよいです。
- 色 1 のスライムを捕まえて飼う。 1 秒掛かる。
- 魔法を唱える。 スライムの色が 1 → 2 と変わる。 10 秒掛かる。
- 色 1 のスライムを捕まえて飼う。 1 秒掛かる。
入力例 2
3 10 100 1 100
出力例 2
23
次のように操作を行えばよいです。
- 色 2 のスライムを捕まえて飼う。 1 秒掛かる。
- 魔法を唱える。 スライムの色が 2 → 3 と変わる。 10 秒掛かる。
- 色 2 のスライムを捕まえて飼う。 1 秒掛かる。
- 魔法を唱える。 スライムの色が 3 → 1，2 → 3 とそれぞれ変わる。 10 秒掛かる。
- 色 2 のスライムを捕まえて飼う。 1 秒掛かる。
入力例 3
4 10 1 2 3 4
出力例 3
10
次のように操作を行えばよいです。
- 色 1 のスライムを捕まえて飼う。 1 秒掛かる。
- 色 2 のスライムを捕まえて飼う。 2 秒掛かる。
- 色 3 のスライムを捕まえて飼う。 3 秒掛かる。
- 色 4 のスライムを捕まえて飼う。 4 秒掛かる。
Score : 400 points
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
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.
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.