Maximize the Acceleration

Interview

Time limit1sMemory limit128 MB

Summary

Given N parts that each add force and mass, choose the subset maximizing total force divided by total mass, breaking ties by smaller mass.

Level: Medium4 of 10
Topics: Brute force, Bit manipulation, Greedy, Math
Solved: No attempts yet

Problem

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$

Input

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

Output

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.

Examples3

Example 1

Input

Expected output

2
3
4

Example 2
Input
```
10 1 1
21 2
```
Expected output
```
1
```
Example 3
Input
```
10 1 1
20 2
```
Expected output
```
NONE
```