P10072 [GDKOI2024 Junior] Farming Jungle I

Zayin is a wizard who fights monsters. This time, he will face $n$ monsters standing in a line, where the $i$-th monster has health $a_i$. Zayin attacks first using one type of attack. After the attack, all monsters with health less than or equal to $0$ die. After each time Zayin attacks, all surviving monsters deal $1$ point of damage to Zayin. The above process repeats until Zayin kills all monsters. Zayin has three types of attacks: - Normal Attack: Costs $0$ energy. Choose one monster and reduce its health by $1$. - "Tianyinbo": Costs $1$ energy. Choose one monster and reduce its health by $2$. - "Tianleipo": Costs $1$ energy. Reduce the health of all monsters by $1$. Now Zayin has $m$ energy in total. He wants to know, under the optimal strategy, the minimum amount of health he will lose to defeat the $n$ monsters.

The first line contains two positive integers $n, m(1 \leq n, m \leq 10^5)$, where $n$ is the number of monsters and $m$ is the amount of energy Zayin has. 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 health of the $i$-th monster.

Output one integer in one line, representing the answer.

For $30\%$ of the testdata, $1 \leq n, m \leq 5$. For another $15\%$ of the testdata, $m = 0$. For another $15\%$ of the testdata, all $a_i$ are equal. For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $0 \leq m \leq 10^5$, $1 \leq a_i \leq 10^9$. Translated by ChatGPT 5