Description

小明是一名宠物收集者。在这个魔法世界里，有 $N$ 种不同颜色的魔法宠物。一开始，小明没有任何宠物。小明的目标是同时拥有所有颜色的魔法宠物。

小明可以进行以下两种操作：

• 选择一种自己还没有的颜色 $i$（$1\leqslant i\leqslant N$），捕捉一只颜色为i的宠物。这个操作需要 $a_i$ 秒。

• 施放转换魔法。此时，对于现在拥有的每一种宠物，颜色为 $i$（$1≤i\leqslant N-1$）的宠物会变成颜色 $i+1$，颜色为 $N$ 的宠物会变成颜色 $1$。这个操作需要 $x$ 秒。

请你求出小明最少需要多少秒，才能同时拥有所有颜色的魔法宠物。

Format

Input

第一行两个正整数 $N,x$。

第二行 $N$ 个正整数，表示 $a_1,a_2,...,a_N$。

Output

一行一个整数，表示最少需要的时间。

Samples

2 10
1 100

12

3 10
100 1 100

23

4 10
1 2 3 4

10

Limitation

$1\mathrm{s},512\mathrm{MB}$

Subtasks

对于 $100\%$ 的数据，$2\leqslant N\leqslant 2000$，$1\leqslant a_x,\leqslant 10^{9}$。