题目描述

高桥君住在异世界。在这个世界里，有 $N$ 种颜色的史莱姆。一开始，高桥君没有饲养任何颜色的史莱姆。高桥君的目标是要同时饲养所有颜色的史莱姆。

高桥君可以进行以下两种操作：

• 选择一种自己还没有饲养的颜色 $i$（$1 \leq i \leq N$），捕捉并饲养一种颜色为 $i$ 的史莱姆。这个操作需要 $a_i$ 秒。
• 施放魔法。此时，对于现在饲养的每一种史莱姆，颜色为 $i$（$1 \leq i \leq N-1$）的史莱姆会变成颜色 $i+1$，颜色为 $N$ 的史莱姆会变成颜色 $1$。这个操作需要 $x$ 秒。

请你求出高桥君最少需要多少秒，才能同时饲养所有颜色的史莱姆。

输入格式

输入以如下格式从标准输入读入：

$N$ $x$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

输出高桥君最少需要多少秒，才能同时饲养所有颜色的史莱姆。

样例 1

输入

2 10
1 100

输出

12

样例 2

输入

3 10
100 1 100

输出

23

样例 3

输入

4 10
1 2 3 4

输出

10

说明/提示

限制条件

• $2 \leq N \leq 2,000$
• $a_i$ 是整数
• $1 \leq a_i \leq 10^9$
• $x$ 是整数
• $1 \leq x \leq 10^9$

样例解释 1

可以按如下方式操作：

• 捕捉并饲养颜色 $1$ 的史莱姆，耗时 $1$ 秒。
• 施放魔法，史莱姆颜色 $1 \to 2$，耗时 $10$ 秒。
• 捕捉并饲养颜色 $1$ 的史莱姆，耗时 $1$ 秒。

样例解释 2

可以按如下方式操作：

• 捕捉并饲养颜色 $2$ 的史莱姆，耗时 $1$ 秒。
• 施放魔法，史莱姆颜色 $2 \to 3$，耗时 $10$ 秒。
• 捕捉并饲养颜色 $2$ 的史莱姆，耗时 $1$ 秒。
• 施放魔法，史莱姆颜色 $3 \to 1$，$2 \to 3$，耗时 $10$ 秒。
• 捕捉并饲养颜色 $2$ 的史莱姆，耗时 $1$ 秒。

样例解释 3

可以按如下方式操作：

• 捕捉并饲养颜色 $1$ 的史莱姆，耗时 $1$ 秒。
• 捕捉并饲养颜色 $2$ 的史莱姆，耗时 $2$ 秒。
• 捕捉并饲养颜色 $3$ 的史莱姆，耗时 $3$ 秒。
• 捕捉并饲养颜色 $4$ 的史莱姆，耗时 $4$ 秒。

由 ChatGPT 4.1 翻译