benzinska — COCI CONTEST_#4
Task type: batch | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 13
Algorithms: greedy, sorting

## Task Benzinska

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.

![](./_page_0_Picture_5.jpeg)

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.

## Input

In the first line of input, there are three integers $n$, $D$, and $X$ ($1 \le n \le 2 * 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.

## Output

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).

## Scoring

| Subtask | Points | Constraints                |
|---------|--------|----------------------------|
| 1       | 15     | $y_i = y_j$ for every i, j |
| 2       | 30     | $n \le 1000$              |
| 3       | 25     | No additional constraints. |

## Probni primjeri

| input                             | input                                | input                         |
|-----------------------------------|--------------------------------------|-------------------------------|
| 5 5 12<br>3 4 7 8 11<br>3 2 1 2 1 | 5 10 40<br>1 20 30 2 38<br>7 7 7 7 7 | 4 5 12<br>3 6 9 10<br>2 1 2 2 |
| output                            | output                               | output                        |
| 3                                 | 5                                    | -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

![](./_page_1_Picture_0.jpeg)

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.

Starter code: