AT_agc004_b [AGC004B] Colorful Slimes

高桥君住在异世界。在这个世界里，有 $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$

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

## 限制条件 - $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 翻译