AT_bcu30_2019_a.Wolf Keyboard

在某个世界中，有 $N$ 种不同的字符被使用。此外，这个世界的键盘上有 $K$ 个字符键和 $1$ 个 Shift 键。
但是，字符的种类数比键盘上的字符键数多，但又少于字符键数的两倍。
也就是说，满足 $K < N < 2K$。

为此，可以通过以下方式输入所有种类的字符：

• $N$ 种字符中，有 $K$ 种字符可以通过按下某个字符键一次输入一个字符。
• 剩下的 $N-K$ 种字符可以通过同时按下 Shift 键和某个字符键一次输入一个字符。

现在，Cybozu 的高桥先生需要输入一份文档。该文档中，第 $i$ 种字符出现了 $a_i$ 次。
通过合理地分配字符与按键的对应关系，希望使按键的总次数最小。
其中，同时按下 Shift 键和字符键算作按键 $2$ 次。

请输出按键总次数的最小值。

输入通过标准输入以以下格式给出。

$N$ $K$ $a_1$ $a_2$ $\cdots$ $a_N$

请输出按键总次数的最小值。

限制条件

• $2 \leq K \leq 50$
• $K < N < 2K$
• $0 \leq a_i \leq 100$（$1 \leq i \leq N$）

样例解释 1

将第 $1$、$2$、$5$、$6$ 种字符分配为仅通过字符键输入，将第 $3$、$4$ 种字符分配为通过 Shift 键和字符键同时输入，则按键总次数最小，为 $9 + 7 + 1 \times 2 + 1 \times 2 + 9 + 8 = 37$。

由 ChatGPT 4.1 翻译