영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
A small army of N monsters is just outside Tästerås! Now it is up to the wizard Theodor to defeat them and save the city. Each monster has a certain amount of life points. To damage the monsters, Theodor can fire magical explosions. Each time he fires an explosion, he targets a specific monster. Then, the following occurs:
- All monsters lose A life points due to the explosion.
- The monster that Theodor targeted loses an additional S life points, as it is at the center of the explosion. Thus, the targeted monster loses a total of S + A life points from that explosion.
He can freely choose which monster to target each time he fires an explosion. Since firing explosions is exhausting, he wants to know the minimum number of explosions he needs to fire to defeat all the monsters if he targets them optimally.
Input
The first line of input contains three integers, N (1 ≤ N ≤ 10), S (1 ≤ S ≤ 10^9), and A (0 ≤ A ≤ 10^9), which are the three values described above.
The second line contains N integers h_1, h_2, …, h_N (1 ≤ h_i ≤ 10^9), representing the life points of each monster.
Output
Print the minimum number of explosions Theodor needs to fire to defeat all the monsters.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 20 | A = 0 |
| 2 | 35 | h_i ≤ 100 |
| 3 | 5 | A ≤ 10^5 |
| 4 | 40 | No additional constraints. |
Explanation of Sample 1
An optimal way to fire explosions is as follows:
- Fire an explosion at the monster with 7 life points. The monsters now have
4,1,2life points remaining. - Fire an explosion at the monster with 4 life points remaining. The monster with 1 life point is defeated. The remaining monsters now have
1,1life points. - Fire an explosion at any of the remaining monsters. Now all the monsters have been defeated, and Theodor is done.
예제
예제 1
3 2 1 7 2 3
3
예제 2
4 3 2 7 8 9 10
4