分数: 400 点
问题陈述
Snuke 生活在另一个世界,那里的史莱姆是真实的生物,由一些人饲养。 史莱姆进来了 N 颜色。这些颜色方便地编号 1 通过 N。 Snuke 目前没有史莱姆。他的目标是将所有颜色的史莱姆混合在一起。
Snuke 可以执行以下两个操作:
-
选择颜色 i (1≤i≤N),这样他目前没有彩色的史莱姆 i,并捕捉彩色史莱姆 i。这个动作让他 a_i 秒。
-
施放一个咒语,改变他当前拥有的所有史莱姆的颜色。粘液的颜色 i (1≤i≤N-1) 将变成颜色 i+1,以及颜色中史莱姆的颜色 N 将变成颜色 1。这个动作让他 x 秒。
求 Snuke 总共需要拥有史莱姆的最短时间 N 颜色。
约束
- 2≤N≤2,000
- a_i 是整数。
- 1≤a_i≤10^9
- x 是一个整数。
- 1≤x≤10^9
输入
输入由标准输入按以下格式给出:
N x a_1 a_2 ... a_N
输出
求 Snuke 总共需要拥有史莱姆的最短时间 N 颜色。
示例输入 1
2 10 1 100
示例输出 1
12
Snuke 的作用如下:
- 抓住彩色史莱姆 1。这需要 1 第二。
- 施展咒语。粘液的颜色发生变化: 1 → 2。这需要 10 秒。
- 抓住彩色史莱姆 1。这需要 1 第二。
示例输入 2
3 10 100 1 100
示例输出 2
23
Snuke 的作用如下:
- 抓住彩色史莱姆 2。这需要 1 第二。
- 施展咒语。粘液的颜色发生变化: 2 → 3。这需要 10 秒。
- 抓住彩色史莱姆 2。这需要 1 第二。
- 施放 soell。每个史莱姆的颜色都会发生变化: 3 → 1, 2 → 3。这需要 10 秒。
- 抓住彩色史莱姆 2。这需要 1 第二。
示例输入 3
4 10 1 2 3 4
示例输出 3
10
Snuke 的作用如下:
- 抓住彩色史莱姆 1。这需要 1 第二。
- 抓住彩色史莱姆 2。这需要 2 秒。
- 抓住彩色史莱姆 3。这需要 3 秒。
- 抓住彩色史莱姆 4。这需要 4 秒。