Description

Bessie 正在为即将到来的赛车比赛作准备。

她有一辆赛车，质量为 $M$，且可以提供 $F$ 的力。现在她想要给这辆赛车安装一些零件（总共有 $N$ 个零件），每个零件具有属性 $M_i$ 和 $F_i$，表示其质量以及可以提供的力。

设 $X_i = 1$ 或 $0$，表示第 $i$ 个零件选或不选。在最大化

$$\dfrac{F+\sum_{i=1}^{n}X_i \cdot F_i}{M+\sum_{i=1}^{n}X_i \cdot M_i}$$

的前提下最小化

$$\sum_{i=1}^{n}X_i \cdot M_i + M.$$

Input Format

第一行是三个用空格分开的正整数 $F,\,M,\,N$。

接下来 $N$ 行，每行两个用空格分开的正整数，第 $i+1$ 行的两个数代表 $F_i$ 和 $M_i$。

Output Format

输出包含 $P$ 行，表示 Bessie 需要安装的 $P$ 个零件的下标。若 Bessie 不需要给这辆车安装零件，输出 NONE。

输出应按递增顺序给出，如果最佳零件集为 $\{2,4,6,7\}$，则输出应按 $2,4,6,7$ 的顺序，而不是 $4,2,7,6$ 的顺序。解决方案将是唯一的。

1500 100 4 
250 25 
150 9 
120 5 
200 8 

2 
3 
4 

Hint

数据范围

$1 \le N \le 10\,000$；

$1 \le M,M_i\le1\,000$；

$1 \le F,F_i \le 1\,000\,000$。

感谢 @tyqtyq 提供的翻译。