Problem Description

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.

Input Format

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 Format

Output one integer in one line, representing the answer.

3 4
2 4 4

6

Hint

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