Need For Speed

Bessie is tuning her race car for the upcoming Grand Prix and wants to buy extra parts to make it faster.

Right now the car has mass $M$ ($1 \le M \le 1000$) and can push itself forward with force $F$ ($1 \le F \le 1{,}000{,}000$). By Newton's second law $F = MA$, so its acceleration is $A = F / M$.

The parts store sells $N$ ($1 \le N \le 10{,}000$) parts numbered $1$ through $N$, with at most one of each in stock. Buying part $i$ adds force $F_i$ ($1 \le F_i \le 1{,}000{,}000$) and mass $M_i$ ($1 \le M_i \le 1000$). Bessie may buy any subset of the parts, including none of them.

If Bessie installs the parts in a set $S$, the car's total force becomes $F + \sum_{i \in S} F_i$ and its total mass becomes $M + \sum_{i \in S} M_i$, giving acceleration

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

Choose the set of parts that maximizes this acceleration. If several sets achieve the same maximum acceleration, choose the one with the smallest total mass. The optimal set is guaranteed to be unique.

For example, installing a single part with force $f$ and mass $m$ changes the acceleration to $(F + f) / (M + m)$.

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

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

Print the 1-based indices of the parts Bessie should install, in increasing order, one per line. If installing no part is optimal, print NONE.