Diet Plan

Interview

Time limit1sMemory limit2048 MB

Summary

Given daily milk needs P_i, M mL of milk, and K biscuits, find the maximum number of days the diet can last.

Level: Medium4 of 10
Topics: Greedy, Heap
Solved: No attempts yet

Problem

You have a diet plan for the next $N$ days (numbered from $1$ to $N$ ). During day $i$ , you need to drink exactly $P_i$ mL of milk. Alternatively, you can consume a biscuit instead, as a replacement for milk on that day.

Currently, you only have $M$ mL of milk and $K$ biscuits. If there is not enough milk to drink on a day and you run out of biscuits, then your diet plan stops.

Determine the maximum number of days you can maintain your diet plan.

Input

The first line consists of three integers $N$ , $M$ , $K$ ( $1 \le N \le 100$ ; $0 \le M, K \le 100$ ).

The next line consists of $N$ integers $P_i$ ( $1 \le P_i \le 100$ ).

Output

Output a single integer representing the maximum number of days you can maintain your diet plan.

Examples4

Example 1
Input
```
7 100 2
70 30 20 40 50 40 10
```
Expected output
```
5
```
Example 2
Input
```
7 70 1
70 30 40 20 50 10 60
```
Expected output
```
3
```
Example 3
Input
```
7 0 100
100 100 100 100 100 100 100
```
Expected output
```
7
```
Example 4
Input
```
7 0 0
1 1 1 1 1 1 1
```
Expected output
```
0
```