P10074 [GDKOI2024 Junior] Farming Monsters III

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.

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 one integer, the minimum number of attacks.

**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