Spell of Weakness
Snuke is playing computer games again. He encounters N enemies in the game.
The i-th enemy has Ai HP (Health Points), and can take Ai points of damage before being defeated.
Snuke can distribute 1 point of damage to a single enemy in an attack. Snuke has D attacks. He can also cast K spells of weakness which will half the HP of one enemy (rounded down to the nearest integer).
Each enemy can have at most one spell of weakness applied on it.
Snuke wants to know the maximum number of enemies he can defeat.
- 1 ≤ K ≤ N ≤ 106
- 1 ≤ D ≤ A1+A2+...+AN
- 0 ≤ Ai ≤ 109
Subtask 1 (20%): K = 1
Subtask 2 (20%): 1 ≤ K ≤ N ≤ 2000
Subtask 3 (60%): No additional constraints.
Subtask 4 (0%): Sample Testcases
The input is given from Standard Input in the following format:
N D K
A1 A2 ... AN
The output should contain a single integer, the number of enemies Snuke can defeat with K spells of weakness.
Sample Input 1
3 5 2
2 4 7
Sample Output 1
Snuke can cast the spells of weakness on the 2nd and 3rd enemies and deal 2+3 = 5 points of damage.
Sample Input 2
3 5 2
1000 1000 1000
Sample Output 2
No matter how Snuke casts the spells of weakness, he cannot defeat any of the enemies.