AtCoder Grand Contest 004

B - Colorful Slimes


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 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 秒掛かる。
  • 魔法を唱える。 スライムの色が 12 と変わる。 10 秒掛かる。
  • 1 のスライムを捕まえて飼う。 1 秒掛かる。

入力例 2

3 10
100 1 100

出力例 2

23

次のように操作を行えばよいです。

  • 2 のスライムを捕まえて飼う。 1 秒掛かる。
  • 魔法を唱える。 スライムの色が 23 と変わる。 10 秒掛かる。
  • 2 のスライムを捕まえて飼う。 1 秒掛かる。
  • 魔法を唱える。 スライムの色が 3123 とそれぞれ変わる。 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: 12. 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: 23. This takes 10 seconds.
  • Catch a slime in color 2. This takes 1 second.
  • Cast the soell. The color of each slime changes: 31, 23. 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.

Submit提出する