Spell Of Weakness

Problem Statement

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 do 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.

Constraints

  • 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

Input

The input is given from Standard Input in the following format:

N D K
A1 A2 ... AN

Output

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

2

Explanation

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

0

Explanation

No matter how Snuke casts the spells of weakness, he cannot defeat any of the enemies.


Submitting to 'Spell Of Weakness'


You're not logged in! Click here to login


Submitting to 'Spell Of Weakness'


You're not logged in! Click here to login


Submitting .cpp to 'Spell Of Weakness'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 57
Your best score: 0
Source: Dunjudge Archive (dantoh)

Subtask Score
1 20
2 20
3 60
4 0