[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 $ 秒掛かる。