Buying Gas

Time limit1sMemory limit128 MB

Summary

Choose the fewest gas stations to stop at so the car never runs out of gas over a trip of length d with tank range 10n.

Level: Medium5 of 10
Topics: Greedy, Sorting, Array
Solved: No attempts yet

Problem

You are planning a long car trip. You must choose the gas stations at which to stop so that the car never runs out of gas, while stopping to fill up as few times as possible.

The car's gas tank holds $n$ litres, and the car uses $0.1$ litres of gas for every kilometre travelled, so a full tank is enough to drive at most $10n$ km. The car begins the trip with a full tank.

There are $m$ gas stations along the route; each has a distance from the starting point and a price. The destination is $d$ kilometres from the start.

Find a set of gas stations to stop at so that the car reaches the destination without ever running out of gas and the number of stops is as small as possible.

Input

The first line contains three integers $n$ , $m$ , and $d$ : the capacity of the gas tank in litres, the number of gas stations along the route, and the total length of the trip in kilometres, with $0 < n \le 100$ , $0 \le m \le 100000$ , and $0 \le d \le 100000$ .

Each of the following $m$ lines contains two integers: the distance in kilometres from the starting point of the trip to the gas station, and the price of gas at that station in tenths of a cent per litre.

The car begins the trip with a full tank of gas and uses $0.1$ litres of gas for each kilometre travelled.

Output

Output a single integer: the number of gas stations in an optimal set of stops (that is, the minimum number of times the car must stop to fill up) so that it completes the trip without ever running out of gas. If it is not possible to make the trip without running out of gas, output $-1$ instead.

Examples3

Example 1
Input
```
50 2 1000
500 1293
750 1337
```
Expected output
```
1
```
Example 2
Input
```
10 0 100
```
Expected output
```
0
```
Example 3
Input
```
5 1 200
100 900
```
Expected output
```
-1
```