Minimum Restaurant Stops on the Number Line

Malnar starts at the origin on the number line (x = 0) and wishes to reach x = X. Initially, he has D units of energy. Each unit distance traveled consumes one unit of energy, and at no point may his energy drop below 0.

There are n restaurants. The i-th restaurant is located at x = x_i and offers an energy boost of y_i when visited. Each restaurant can be used at most once (note that different restaurants may share the same position).

Your task is to determine the minimum number of restaurants at which Malnar needs to take a meal in order to reach his destination. If it is impossible for him to reach x = X, output -1.

Note: All formulas provided are in LaTeX format. For example, the starting point is given as \( x=0 \), and the destination as \( x=X \).

inputFormat

The first line contains three integers: \( X \), \( D \), and \( n \) (destination, initial energy, and number of restaurants).

Each of the next \( n \) lines contains two integers \( x_i \) and \( y_i \) representing the position of the restaurant and the energy gained if visited.

outputFormat

Output a single integer: the minimum number of restaurants at which Malnar must take a meal to reach \( x=X \). If it is not possible, output \( -1 \).

sample

10 5 3
3 4
5 3
8 3

2