問題文

ある世界では N 種類の文字が使われています。また、この世界のキーボードには、K 個の文字キーと 1 個の Shift キーがあります。 しかし、 文字の種類数はキーボードの文字キーの数より多く、文字キーの数の 2 倍より少ないことが分かっています。 すなわち、K < N < 2K を満たします。

そこで、以下のようにして全種類の文字を入力できるようにします。

• N 種類の文字のうち K 種類の文字は、ある文字キーを 1 回押すことで 1 文字入力される。
• 残りの N-K 種類の文字は、Shift キーとある文字キーを 1 回同時に押すことで 1 文字入力される。

今、サイボウズの高橋さんはとある文書を入力することになりました。この文書には、i 種類目の文字が a_i 個含まれています。 適切に文字とキーを割り当てることによって、キーを押す回数の合計を最小化したいです。ただし、Shift キーと文字キーを同時に押すのを 2 回押したとカウントします。

キーを押す回数の合計の最小値を求めてください。

制約

• 2 ≤ K ≤ 50
• K < N < 2K
• 0 ≤ a_i ≤ 100 (1 ≤ i ≤ 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