Maximize the Acceleration

Bessie is tuning her race car for an upcoming Grand Prix. Right now the car has mass $M$ and pushes itself forward with force $F$. A performance shop sells $N$ upgrade parts numbered $1$ through $N$. The shop stocks at most one of each part, so Bessie may install any subset of the parts (possibly none).

Installing part $i$ adds force $F_i$ and mass $M_i$ to the car. By Newton's second law $F = M \cdot A$, the car's acceleration equals its total force divided by its total mass. If Bessie installs a set $S$ of parts, the acceleration becomes

$$A = \frac{F + \sum_{i \in S} F_i}{M + \sum_{i \in S} M_i}.$$

For example, adding a single part with force $150$ and mass $9$ to a car with $F = 1500$ and $M = 100$ raises the acceleration from $15$ to $(1500 + 150) / (100 + 9) \approx 15.14$.

Bessie wants to pick the set of parts that maximizes the acceleration. If several different sets reach the same maximum acceleration, she prefers the set with the smallest total mass. Under these two rules the best set of parts is unique.

Constraints

• $1 \le M \le 1000$
• $1 \le F \le 1{,}000{,}000$
• $1 \le N \le 20$
• $1 \le F_i \le 1{,}000{,}000$
• $1 \le M_i \le 1000$

The first line contains three space-separated integers $F$, $M$, and $N$.

Each of the next $N$ lines contains two space-separated integers $F_i$ and $M_i$: the force and mass added by part $i$.

Print the indices of the parts Bessie should install, one per line, in increasing order. If she should install no parts at all, print NONE.