지금 자면 꿈을 꾸지만

면접 대비

시간 제한2초메모리 제한1024 MB

요약

과제 N개의 마감 시각이 주어질 때, 잠을 BX만큼 자고 과제 하나에 A-X를 쓰도록 X를 골라 마감을 지키는 과제 수의 최댓값을 구합니다.

난이도: 쉬움10점 중 3점
유형: 정렬, 그리디, 완전 탐색
정답자: 아직 제출이 없습니다

문제

"지금 자면 꿈을 꾸지만, 지금 공부하면 꿈을 이룬다."라는 말이 있습니다. 하지만 실버의 생각은 조금 다릅니다. 실버는 잠을 잘 자서 공부의 효율을 높이는 것이 중요하다고 생각합니다. 과제가 많았던 실버는 잠을 적당히 자서 최대한 많은 과제를 해내려고 합니다.

실버에게는 $N$ 개의 과제가 있고, $i$ 번째 과제의 기한은 $T_i$ 입니다. 실버는 시각 0부터 시작해서 원하는 시각에 원하는 과제를 하나 골라 진행할 수 있습니다. 과제는 한 번에 하나만 진행할 수 있고, 진행 중인 과제를 마치기 전에는 다른 과제를 시작할 수 없습니다. 과제 하나를 완료하는 데는 $A$ 만큼의 시간이 걸립니다.

실버는 0 이상 $A-1$ 이하의 정수 $X$ 를 고른 다음, $BX$ 만큼 잠을 잘 수 있습니다. 잠을 잔 뒤에는 과제 하나를 완료하는 데 $(A-X)$ 만큼의 시간이 걸립니다. 잠은 최대 한 번만 잘 수 있고, 과제를 진행하는 도중에는 잠을 잘 수 없습니다. 시각 0부터 잠을 잘 수도 있습니다.

실버는 기한 내에 완료하는 과제의 수를 최대화하려고 합니다. $i$ 번째 과제를 정확히 시각 $T_i$ 에 완료한 경우도 기한 내에 완료한 것으로 봅니다. 기한 내에 완료할 수 있는 과제의 최대 개수를 구해 봅시다.

입력

첫 줄에 과제의 수 $N$ , 과제 하나를 완료하는 데 걸리는 초기 시간 $A$ , 과제 완료 시간 단축의 기준이 되는 정수 $B$ 가 공백으로 구분되어 주어집니다. ( $1 \le N, A, B \le 100$ )

둘째 줄에 각 과제의 기한을 나타내는 $N$ 개의 정수 $T_1, T_2, \cdots, T_N$ 이 공백으로 구분되어 주어집니다. ( $1 \le T_i \le 10000$ )

입력으로 들어오는 모든 수는 정수입니다.

출력

첫 줄에 기한 내에 완료할 수 있는 과제의 최대 개수를 출력합니다.

예제4

예제 1
입력
```
3 40 2
70 90 80
```
예상 출력
```
3
```
예제 2
입력
```
3 40 10
70 90 80
```
예상 출력
```
2
```
예제 3
입력
```
4 30 3
70 75 95 105
```
예상 출력
```
4
```
예제 4
입력
```
8 2 5
2 8 9 10 11 12 13 14
```
예상 출력
```
8
```