Minimizing Zayin's Blood Loss

Zayin, a wizard who fights monsters, is now facing n monsters lined up in a row. The i-th monster has a_i health. The battle proceeds in rounds. In each round,Zayin acts first with one attack and then every monster still alive (ie. with positive health) deals 1 point of damage to him. When an attack is performed, any monster whose health becomes 0 or less dies immediately and does not retaliate that round.

Zayin has three attack options:

• Normal Attack: Costs 0 energy. Choose one monster and reduce its health by 1.
• Sonic Wave: Costs 1 energy. Choose one monster and reduce its health by 2.
• Thunder Strike: Costs 1 energy. Reduce the health of all monsters by 1.

Initially, Zayin has m energy. He wants to plan his attacks optimally in order to kill all monsters while minimizing the total damage he receives. The damage received in each round equals the number of monsters alive at the start of that round. Note that if a monster is killed in a round by Zayin’s attack it will not deal damage in that round.

Task. Compute the minimum total damage (i.e. blood loss) Zayin can receive if he follows an optimal strategy.

Some useful remarks:

• You may choose in each round one of the three attacks. The attacks that cost energy (Sonic Wave and Thunder Strike) reduce the energy by 1 per use. Normal Attack does not cost any energy.
• It is always allowed to use a Normal Attack even if energy is 0.
• An attack’s effect occurs immediately. In particular, after Zayin’s attack in a round, any monster with non–positive health is considered dead and will not deal damage that round.
• For example, if a monster has health h then using only Normal Attacks on it requires h rounds to kill, while using Sonic Waves optimally one may need only \(\lceil h/2 \rceil\) rounds (but each Sonic Wave costs energy).

Hint. An optimal strategy balances the use of individual attacks and attacks that affect all monsters. One natural idea is to decide beforehand how many rounds to use Thunder Strike (each costing 1 energy and lowering the health of every monster by 1) and then finish off the remaining health on each monster with targeted attacks – either Normal Attack (costs 0 energy, reduces health by 1) or Sonic Wave (costs 1 energy, reduces health by 2). For each monster with initial health a_i and if X Thunder Strikes are used, the remaining health is max(a_i − X, 0). The minimal number of targeted rounds needed to finish a monster (if sonic is used optimally) is \(\lceil \frac{max(a_i-X,0)}{2} \rceil\) while if no extra energy is used one needs max(a_i − X, 0) rounds. Also note that the overall energy constraint is that the total energy used by Thunder Strike and Sonic Wave cannot exceed m.

One correct solution is to try all possible choices for the number (X) of Thunder Strikes (with 0 \le X \le min(m, max_i a_i)) and then for each, compute two candidate values for the total damage (note that the damage is the sum over all rounds of the number of monsters still alive before the attack):

• Candidate 1: Use only Normal Attacks to finish a monster. The rounds needed for monster i is max(a_i − X, 0) and so the contribution is max(a_i − X, 0).
• Candidate 2: Use Sonic Wave optimally. For monster i, if its remaining health is d_i = max(a_i − X, 0), the minimal rounds needed is \(\lceil d_i/2 \rceil\) (each Sonic Wave saves one round compared to a Normal Attack), but the saving is limited by the amount of energy available.

Thus, if we let

[ S(X) = \sum_{i=1}^{n} ; \max(a_i - X, 0), \quad R(X) = \sum_{i=1}^{n} ; \lceil \frac{\max(a_i - X,0)}{2} \rceil, ]

and if we denote by n the number of monsters, then one may show that an achievable total damage is

[ D(X) = n \cdot X + S(X) - \min\Bigl(m - X, ; S(X) - R(X)\Bigr) - n. ]

Taking the minimum over all valid X (i.e. 0 \le X \le m and not exceeding max(a_i)) yields an answer. (Here, the term \(S(X)-R(X)\) represents the maximum total saving in rounds that Sonic Wave can yield.)

Your task is to implement this idea. (Note that if an attempted allocation of energy exceeds m then the candidate strategy is invalid – in that case you may consider the strategy using only Normal Attacks.)

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁹), representing the number of monsters and the energy available to Zayin.

The second line contains n integers a₁, a₂, …, a_n (1 ≤ a_i ≤ 10⁹) – the health values of the monsters.

outputFormat

Output a single integer – the minimum total damage (blood loss) Zayin receives by following an optimal strategy.

sample

1 2
5

2

</p>