Spell Of Weakness

Problem Statement

Snuke is playing computer games again. He encounters N enemies in the game.

The i-th enemy has A_i HP (Health Points), and can take A_i 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).

Snuke wants to know the maximum number of enemies he can defeat.

Constraints

• 1 ≤ K ≤ N ≤ 10⁶
• 1 ≤ D ≤ A₁+A₂+...+A_N
• 0 ≤ A_i ≤ 10⁹

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.