P2989 [USACO10MAR] Need For Speed S

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

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

输出包含 $P$ 行，表示 Bessie 需要安装的 $P$ 个零件的下标。若 Bessie 不需要给这辆车安装零件，输出 `NONE`。 输出应按递增顺序给出，如果最佳零件集为 $\{2,4,6,7\}$，则输出应按 $2,4,6,7$ 的顺序，而不是 $4,2,7,6$ 的顺序。解决方案将是唯一的。

#### 数据范围 $1 \le N \le 10\,000$； $1 \le M,M_i\le1\,000$； $1 \le F,F_i \le 1\,000\,000$。 感谢 @tyqtyq 提供的翻译。