← 返回题目列表

AtCoder · agc004_b

B. 彩色史莱姆

中文机器翻译题面 查看原题

分数: 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 秒。