If You Sleep Now, You Dream

Interview

Time limit2sMemory limit1024 MB

Summary

Given N task deadlines, choose a sleep reduction X so that each task takes A-X time after sleeping BX, and find the most tasks that can finish by their deadlines.

Level: Easy3 of 10
Topics: Sorting, Greedy, Brute force
Solved: No attempts yet

Problem

"If you sleep now, you dream, but if you study now, you achieve your dream." People say this, but Silver thinks differently. Silver believes that sleeping well raises study efficiency, and that matters most. Silver has many assignments and plans to finish as many as possible by sleeping a moderate amount.

Silver has $N$ tasks, and the deadline of the $i$ -th task is $T_i$ . Silver starts at time 0 and can choose any task to work on at any moment. Only one task can be in progress at a time, and Silver cannot start another task before finishing the current one. Finishing one task takes $A$ units of time.

Silver chooses an integer $X$ with $0 \le X \le A-1$ , then can sleep for $BX$ units of time. After sleeping, finishing one task takes $(A-X)$ units of time. Silver can sleep at most once, and cannot sleep while a task is in progress. Silver can also sleep starting at time 0.

Silver wants to maximize the number of tasks finished by their deadlines. A task finished exactly at time $T_i$ counts as finished on time. Find the maximum number of tasks that can be finished by their deadlines.

Input

The first line contains the number of tasks $N$ , the initial time $A$ needed to finish one task, and the integer $B$ that sets the reduction rate, separated by spaces. ( $1 \le N, A, B \le 100$ )

The second line contains $N$ integers $T_1, T_2, \cdots, T_N$ giving the deadline of each task, separated by spaces. ( $1 \le T_i \le 10000$ )

All numbers in the input are integers.

Output

The first line prints the maximum number of tasks that can be finished by their deadlines.

Examples4

Example 1
Input
```
3 40 2
70 90 80
```
Expected output
```
3
```
Example 2
Input
```
3 40 10
70 90 80
```
Expected output
```
2
```
Example 3
Input
```
4 30 3
70 75 95 105
```
Expected output
```
4
```
Example 4
Input
```
8 2 5
2 8 9 10 11 12 13 14
```
Expected output
```
8
```