题目描述

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$秒钟。
• 施放咒语。每个史莱姆的颜色改变：$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$秒钟。