#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### 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*points of damage before being defeated.

_{i}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.

### Constraints

- 1 ≤ K ≤ N ≤ 10
^{6} - 1 ≤ D ≤ A
_{1}+A_{2}+...+A_{N} - 0 ≤ A
_{i}≤ 10^{9}

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:

NDKA_{1}A..._{2}A_{N}

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 20 | 19 | 1s | 256MB | Minimum |

2 | 20 | 19 | 1s | 256MB | Minimum |

3 | 60 | 19 | 1s | 256MB | Minimum |

4 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o spellofweakness -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512