Problem Description

Zayin is a wizard fighting monsters. This time, he faces $n$ monsters standing in a row, where the $i$-th monster has $a_i$ health points.

Due to some mysterious reason, Zayin cannot control which monster he hits. Specifically, there is a permutation $p$ of length $n$ such that when Zayin attacks the $i$-th monster, he is actually attacking the $p_i$-th monster.

Zayin can choose an integer $k$ in the range $[1, n]$ to reduce the health of the $p_k$-th monster by 1 point. A monster dies when its health drops to 0 or below.

However, Zayin does not know the permutation $p$ nor can he see the remaining health of each monster. He can only know if a monster dies after each attack.

Zayin wants to know, under his optimal strategy, the maximum number of attacks needed to kill $m$ monsters.

Input Format

The first line of input contains two positive integers $n, m$ ($1 \leq m \leq n \leq 2000$), where $n$ is the number of monsters and $m$ is the number of monsters Zayin needs to kill.

The second line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$), where $a_i$ represents the health of the $i$-th monster.

Output Format

Output a single integer, the minimum number of attacks.

Sample Input and Output

Sample Input #1

2 1
10 15

Sample Output #1

15

Sample Input #2

2 1
10 30

Sample Output #2

20

Notes/Hints

[Sample Explanation]

In the first sample, Zayin will keep attacking one monster until it dies.

In the second sample, Zayin attacks one monster 10 times first. If it doesn't die, it means he was attacking the monster with 30 health. Then Zayin switches to the other monster and attacks it 10 times, ensuring the other monster dies. Thus, the worst-case scenario requires 20 attacks.

[Data Range]

For $10\%$ of the data, $1 \leq n, m \leq 5$.

For another $20\%$ of the data, all $a_i$ are equal.

For another $30\%$ of the data, $1 \leq m \leq n \leq 500$.

For $100\%$ of the data, $1 \leq m \leq n \leq 2000$, $1 \leq a_i \leq 10^9$.

见题面 Input 部分

见题面 Output 部分