레이팅 미적용The camp in Čakovec has already started, but Mr. Malnar is still visiting Zagreb’s
restaurants. Wanting to burn the calories he consumed, he decided to cycle to
Čakovec.
Mr. Malnar starts his journey from Zagreb (\(x = 0\)) with an initial energy of \(D\)
and wants to reach Čakovec, which is \(X\) meters away from Zagreb (\(x = X\)). Each
meter of the journey requires one unit of energy. To avoid passing out, his energy
must not become negative at any point during the trip.
There are \(n\) restaurants along the way, with the \(i\)-th restaurant located at the \(x_{i}-th\) meter from the
starting point. Multiple restaurants can be located at the same position. If Mr. Malnar decides to dine at
the \(i\)-th restaurant, his energy increases by \(y_{i}\). He may not eat at the same restaurant multiple times.
Help him determine the minimum number of restaurants he must dine at to safely reach Čakovec.
In the first line of input, there are three integers \(n\), \(D\), and \(X\) (\(1 \le n \le 2 \cdot 10^{5}\), \(1 \le D\), \(X \le 10^{9}\)),
representing the number of restaurants, the initial energy, and the distance between the cities.
In the second line of input, there are \(n\) integers \(x_{i}\) (\(1 \le x_{i} < X\)), representing the positions of the
restaurants.
In the third line of input, there are \(n\) integers \(y_{i}\) (\(1 \le y_{i} \le 10^{9}\)), representing the energy Mr. Malnar gains
by dining at each respective restaurant.
In a single line of output, print the minimum number of restaurants Mr. Malnar must dine at to safely
reach Čakovec. If it is not possible to reach Čakovec, print ’-1’ (without quotes).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 15점 | \(y_{i} = y_{j}\) for every \(i\), \(j\) |
2 | 30점 | \(n \le 1\,000\) |
3 | 25점 | No additional constraints. Probni primjeri input 5 5 12 3 4 7 8 11 3 2 1 2 1 output 3 input 5 10 40 1 20 30 2 38 7 7 7 7 7 output 5 input 4 5 12 3 6 9 10 2 1 2 2 outp\(ut -1\) Clarification of the first example: At \(x = 3\), Mr. Malnar will have 2 energy units left. At the first restaurant, he will dine, and his energy will increase to \(2 + 3 = 5\). At \(x = 4\), he will have 4 energy units left. At the second restaurant, he will dine, and his energy will increase to \(4 + 2 = 6\). At \(x = 8\), he will have 2 energy units left. At the fourth restaurant, he will dine, and his energy will increase to \(2 + 2 = 4\). In total, he dined at three restaurants. |
5 5 12
3 4 7 8 11
3 2 1 2 1
3
5 10 40
1 20 30 2 38
7 7 7 7 7
5
4 5 12
3 6 9 10
2 1 2 2
-1