Zayin is a wizard who fights monsters. This time, he faces $n$ monsters standing in a row, where the $i$-th monster has $a_i$ health points.
Zayin attacks first using one of his attack methods. After the attack, all monsters with health points less than or equal to $0$ die. After Zayin attacks once, all surviving monsters deal $1$ point of damage to Zayin. These steps repeat until Zayin has killed all the monsters.
Zayin has three types of attack methods:
- Normal Attack: Consumes $0$ energy, choose one monster and reduce its health by $1$.
- Sonic Wave: Consumes $1$ energy, choose one monster and reduce its health by $2$.
- Thunderclap: Consumes $1$ energy, reduce the health of all monsters by $1$.
Zayin has a total of $m$ energy. He wants to know the minimum amount of health he will lose to defeat all $n$ monsters under an optimal strategy.
Input
The first line contains two positive integers $n, m$ ($1 \le n, m \le 10^5$), where $n$ is the number of monsters and $m$ is the amount of energy Zayin possesses.
The second line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the health of the $i$-th monster.
Output
Output a single integer representing the answer.
Examples
Input 1
3 4 2 4 4
Output 1
6
Constraints
- For $30\%$ of the data, $1 \le n, m \le 5$.
- For another $15\%$ of the data, $m = 0$.
- For another $15\%$ of the data, all $a_i$ are equal.
- For $100\%$ of the data, $1 \le n \le 10^5, 1 \le m \le 10^5, 1 \le a_i \le 10^9$.