OI题库

【题目描述】

Bessie在为即将来临的汽车大赛准备赛车，它想购买一些附加装备来增强赛车的性能。赛车当前的质量为M(1≤M≤1，000)，具有F (1≤F≤1,000，000)大小的动力。商店里有N(1≤N≤10，000)个装备，编号1…N。Bessie可以随便购买多少个装备，但每个装备只能买一件。

装备P_i可以增加F_i (1≤F_i≤1,000，000)的动力，但同时也增加了M_i(1≤M_i≤1,000)的质量。牛顿运动定律说：F=MA，F是力，M是质量，A是加速度。如果Bessie希望赛车的加速度最大(否则的话希望赛车的质量最轻)，那么它应当购买多少附加装备呢?

例如，一辆赛车的初始值为F=1500，M=100，有4种附加装备：

i F_i M_i

1 250 25

2 150 9

3 120 5

4 200 8

如果只购买装备2，加速度为：(1500+150)/(100+9)=165/109=15.13761。

下表列出了购买装备的各种组合情况，在第1列中，1表示要买，0表示不买。

Parts Aggregate Aggregate

1234 F M F/M

0000 1500 100 15.0000

0001 1700 108 15.7407

0010 1620 105 15.4286

001 1 1820 113 16.1062

0100 1650 109 15.1376

0101 1850 117 15.8120

0110 1770 114 15.5263

011 1 1970 122 16.1475<-最大的F/M

1000 1750 125 14.0000

1001 1950 133 14.6617

1010 1870 130 14.3846

1011 2070 138 15.0000

1100 1900 134 14.179l

1101 2100 142 14.7887

1110 2020 139 14.5324

1111 2220 147 15.1020

因此，最佳的购买方案是2，3，4。

【输入格式】

第1行：3个整数F，M，N

第2…N+I行：第i+l行包含2个整数F_i和M_i

【输出格式】

若干行，每行输出一个要购买的装备的编号，以升序输出。如果不需要购买，则输出'NONE'(不要引号)。

数据保证答案唯一。

【样例输入】

1500 100 4
250 25
150 9
120 5
200 8

【样例输出】

2
3
4

【提示】

在此键入。

【来源】

在此键入。