Race Car Performance Optimization

Bessie wants to maximize the acceleration of her race car by selecting extra parts. The race car initially has a force \(F\) and mass \(M\) so that its acceleration is \(A = \frac{F}{M}\). There are \(N\) available parts; part \(i\) adds force \(F_i\) and mass \(M_i\). If Bessie adds a subset of parts, the new acceleration becomes \(\frac{F+\sum F_i}{M+\sum M_i}\). She wishes to pick the set of parts that maximizes the acceleration. In case of a tie, the combination with the smallest total mass is preferred.

For example, suppose the race car starts with \(F=1500\) and \(M=100\), and four parts are available:

• Part 1: \(F_1=250, \; M_1=25\)
• Part 2: \(F_2=150, \; M_2=9\)
• Part 3: \(F_3=120, \; M_3=5\)
• Part 4: \(F_4=200, \; M_4=8\)

Addition of parts 2, 3, and 4 yields a total force of 1970 and a total mass of 122, resulting in \(\frac{1970}{122} \approx 16.1475\), which is optimal.

inputFormat

The input begins with three integers (F), (M), and (N) (the initial force, mass, and the number of available parts). Following this, there are (N) lines. Each line contains two integers (F_i) and (M_i) representing the additional force and mass of the i-th part.

outputFormat

Output the indices of the selected parts in increasing order, separated by spaces. If no part should be chosen, output the string "NONE".

sample

1500 100 4
250 25
150 9
120 5
200 8

2 3 4