配点 : $400$ 点

問題文

高橋君は異世界に住んでいます。 この世界には $N$ 色のスライムがいます。 最初、高橋君はどの色のスライムも飼っていません。 高橋君の目標は、全色のスライムを一緒に飼うことです。

高橋君は次の $2$ 種類の操作を行えます。

• 今飼っていないスライムの色 $i$ ($1 \leq i \leq N$) をひとつ選ぶ。 色 $i$ のスライムを捕まえて飼う。 この操作には $a_i$ 秒掛かる。
• 魔法を唱える。 すると、今飼っている各スライムについて、色 $i$ ($1 \leq i \leq N-1$) のスライムは色 $i+1$ へ変色する。 ただし、色 $N$ のスライムは色 $1$ へ変色する。 この操作には $x$ 秒掛かる。

高橋君が全色のスライムを一緒に飼うためには、最短で合計何秒掛かるかを求めてください。

制約

• $2 \leq N \leq 2,000$
• $a_i$ は整数である。
• $1 \leq a_i \leq 10^9$
• $x$ は整数である。
• $1 \leq x \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $x$

$a_1$ $a_2$ $...$ $a_N$

出力

高橋君が全色のスライムを一緒に飼うためには、最短で合計何秒掛かるかを出力せよ。

2 10
1 100

12

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

• 色 $1$ のスライムを捕まえて飼う。 $1$ 秒掛かる。
• 魔法を唱える。 スライムの色が $1$ → $2$ と変わる。 $10$ 秒掛かる。
• 色 $1$ のスライムを捕まえて飼う。 $1$ 秒掛かる。

3 10
100 1 100

23

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

• 色 $2$ のスライムを捕まえて飼う。 $1$ 秒掛かる。
• 魔法を唱える。 スライムの色が $2$ → $3$ と変わる。 $10$ 秒掛かる。
• 色 $2$ のスライムを捕まえて飼う。 $1$ 秒掛かる。
• 魔法を唱える。 スライムの色が $3$ → $1$，$2$ → $3$ とそれぞれ変わる。 $10$ 秒掛かる。
• 色 $2$ のスライムを捕まえて飼う。 $1$ 秒掛かる。

4 10
1 2 3 4

10

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

• 色 $1$ のスライムを捕まえて飼う。 $1$ 秒掛かる。
• 色 $2$ のスライムを捕まえて飼う。 $2$ 秒掛かる。
• 色 $3$ のスライムを捕まえて飼う。 $3$ 秒掛かる。
• 色 $4$ のスライムを捕まえて飼う。 $4$ 秒掛かる。