Problem Description

Zayin is a wizard who fights monsters. This time he will face $n$ monsters standing in a line, where the HP of the $i$-th monster is $a_i$.

However, for some mysterious reason, Zayin cannot control which monster he hits. More specifically, there is a permutation $p$ of length $n$. When Zayin attacks the $i$-th monster, he is actually attacking the $p_i$-th monster.

Each time, Zayin may choose an integer $k \in [1, n]$, causing the HP of the $p_k$-th monster to decrease by $1$. When a monster's HP becomes less than or equal to $0$, that monster dies.

However, Zayin does not know what the permutation $p$ is, and he also cannot see the exact remaining HP of each monster. He can only know whether the monster dies after each attack.

Now Zayin wants to know: if he uses the best strategy, in the worst case, how many attacks are needed at most to kill $m$ monsters.

Input Format

The first line 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$ is the HP of the $i$-th monster.

Output Format

Output one integer, the minimum number of attacks.

2 1
10 15

15

2 1
10 30

20

Hint

Sample Explanation

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

In the second sample, Zayin first attacks one monster $10$ times. If it does not die, then it means he is attacking the monster with $30$ HP. At this point, Zayin will choose to attack the second monster. After attacking it $10$ times, the other monster must die, so in the worst case $20$ attacks are needed.

Constraints

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

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

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

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

Translated by ChatGPT 5