Problem Description

In a certain world, $ N $ types of characters are used. Also, the keyboard in this world has $ K $ character keys and $ 1 $ Shift key. However, it is known that the number of character types is more than the number of character keys on the keyboard and less than twice the number of character keys. That is, $ K < N < 2K $ is satisfied.

Therefore, all types of characters can be input as follows:

• $ K $ types of characters out of $ N $ types can be input by pressing a character key once.
• The remaining $ N-K $ types of characters can be input by pressing the Shift key and a character key simultaneously once.

Now, Mr. Takahashi from Cybozu has been tasked with inputting a certain document. This document contains $ a_i $ instances of the $ i $-th type of character. By appropriately assigning characters to keys, we want to minimize the total number of key presses. Note that pressing the Shift key and a character key simultaneously counts as 2 presses.

Find the minimum total number of key presses.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ a_1 $ $ : $ $ a_N $

Output Format

Output the minimum total number of key presses.

Sample Input and Output

Sample Input #1

6 4
9
7
1
1
9
8

Sample Output #1

37

Sample Input #2

8 5
0
5
7
8
7
0
9
3

Sample Output #2

42

Notes/Hints

Constraints

• $2 \leq K \leq 50$
• $ K < N < 2K $
• $0 \leq a_i \leq 100$ ($1 \leq i \leq N$)

Sample Explanation 1

The characters of types 1, 2, 5, and 6 can be input by pressing only the character keys, and the characters of types 3 and 4 can be input by pressing the Shift key and a character key simultaneously. Assigning keys in this way minimizes the total number of key presses, which amounts to $9 + 7 + 1 \times 2 + 1 \times 2 + 9 + 8 = 37$.

见题面 Input 部分

见题面 Output 部分