[AGC004B] Colorful Slimes
题意翻译
现在有一群史莱姆,它们有 $N$ 种颜色。现在你需要搜集齐 $N$ 种颜色,但是只能够使用下面的方法:
1. 选择颜色 $i$,然后花费 $a _ i$ 的代价抓一只颜色为 $i$ 的史莱姆。
2. 施展魔法,让已经抓到的所有的史莱姆的颜色都从 $i$ 变为 $i+1$,代价是 $x$(颜色为 $N$ 的史莱姆的颜色变为 $1$)。
现在要求你以最小的代价搜集齐 $N$ 种颜色,输出最小代价。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc004/tasks/agc004_b
高橋君は異世界に住んでいます。 この世界には $ 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 $
输出格式
高橋君が全色のスライムを一緒に飼うためには、最短で合計何秒掛かるかを出力せよ。
输入输出样例
输入样例 #1
2 10
1 100
输出样例 #1
12
输入样例 #2
3 10
100 1 100
输出样例 #2
23
输入样例 #3
4 10
1 2 3 4
输出样例 #3
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 $ 秒掛かる。