← 返回题目列表

AtCoder · bcu30_2019_a

A. 狼键盘

中文机器翻译题面 查看原题

配点 : 100 点

問題文

在某个世界中, N 使用了种类的文字。此外,在这个世界的键盘上,K 有个文字键和 1 一个 Shift 键。 然而, 文字的种类数比键盘上的文字键还多,并且少于文字键数量的 2 倍。 也就是说,K < N < 2K 成立。

因此,为了能够输入所有种类的文字,将按以下方式进行。

  • N 在种类的文字中, K 种类的文字用某个文字键输入 1 通过回车键 1 可以输入字符。
  • 剩下的 N-K 种类的字符,可以通过同时按 Shift 键和某个字符键 1 来输入。 1 可以输入字符。

现在,Cybozu 的高桥先生需要输入一份文书。在这份文书中,i 种类的字符 a_i 个包含在其中。 通过适当地分配字符和键,可以最小化按键的总次数。但是,同时按 Shift 键和字符键会计算为 2 次按键。

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

制約

  • 2 ≤ K ≤ 50
  • K < N < 2K
  • 0 ≤ a_i ≤ 100 (1 ≤ i ≤ N)

入力

输入将以以下形式从标准输入给出。

N K
a_1
:
a_N

出力

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


入力例 1

6 4
9
7
1
1
9
8

出力例 1

37

1 種類目、2 種類目、5 種類目、6 能通过仅按字符键输入种类的字符,3 種類目、4 通过将种类目文字分配到按住 Shift 键和文字键的同时输入,就可以使按键次数总数最少,按键总次数为 9 + 7 + 1 × 2 + 1 × 2 + 9 + 8 = 37 。


入力例 2

8 5
0
5
7
8
7
0
9
3

出力例 2

42