Buying Gas

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.

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