题目描述

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

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

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

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

输入格式

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

$N$ $x$ $a_1$ $a_2$ $...$ $a_N$

输出格式

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

题目大意

现在有一群史莱姆，它们有 $N$ 种颜色。现在你需要搜集齐 $N$ 种颜色，但是只能够使用下面的方法：

1. 选择颜色 $i$，然后花费 $a _ i$ 的代价抓一只颜色为 $i$ 的史莱姆。
2. 施展魔法，让已经抓到的所有的史莱姆的颜色都从 $i$ 变为 $i+1$，代价是 $x$（颜色为 $N$ 的史莱姆的颜色变为 $1$）。

现在要求你以最小的代价搜集齐 $N$ 种颜色，输出最小代价。

2 10
1 100

12

3 10
100 1 100

23

4 10
1 2 3 4

10

提示

制約

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

Sample Explanation 1

次のように操作を行えばよいです。 - 色 $1$ のスライムを捕まえて飼う。 $1$ 秒掛かる。 - 魔法を唱える。 スライムの色が $1$ → $2$ と変わる。 $10$ 秒掛かる。 - 色 $1$ のスライムを捕まえて飼う。 $1$ 秒掛かる。

Sample Explanation 2

次のように操作を行えばよいです。 - 色 $2$ のスライムを捕まえて飼う。 $1$ 秒掛かる。 - 魔法を唱える。 スライムの色が $2$ → $3$ と変わる。 $10$ 秒掛かる。 - 色 $2$ のスライムを捕まえて飼う。 $1$ 秒掛かる。 - 魔法を唱える。 スライムの色が $3$ → $1$，$2$ → $3$ とそれぞれ変わる。 $10$ 秒掛かる。 - 色 $2$ のスライムを捕まえて飼う。 $1$ 秒掛かる。

Sample Explanation 3

次のように操作を行えばよいです。 - 色 $1$ のスライムを捕まえて飼う。 $1$ 秒掛かる。 - 色 $2$ のスライムを捕まえて飼う。 $2$ 秒掛かる。 - 色 $3$ のスライムを捕まえて飼う。 $3$ 秒掛かる。 - 色 $4$ のスライムを捕まえて飼う。 $4$ 秒掛かる。