## Editorial for Need For Speed

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const maxn=10010;
ep=0.000000001;
var n,ff,mm,r,l,last,x:longint;
re:real;
f,m,d:array[0..maxn] of longint;
dau:array[0..maxn] of boolean;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
i:=l; j:=r; x:=f[(i+j) shr 1]; y:=m[(i+j) shr 1];
repeat
while f[i]*y>m[i]*x do i:=i+1;
while f[j]*y<m[j]*x do j:=j-1;
if i<=j then
begin
t:=f[i]; f[i]:=f[j]; f[j]:=t;
t:=m[i]; m[i]:=m[j]; m[j]:=t;
t:=d[i]; d[i]:=d[j]; d[j]:=t;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;

procedure rf;
var i:longint;
begin
n:=0;
for i:=1 to x do
begin
inc(n);
d[n]:=i;
if ff*m[n]>=f[n]*mm then dec(n);
end;
sort(1,n);
end;

procedure pr;
var i,j,k,cm,cf,z:longint;
begin
re:=ff/mm;
r:=mm; cm:=0; cf:=0;
for k:=1 to n do
begin
cm:=cm+m[k];
cf:=cf+f[k];
if ((abs((ff+cf)/(mm+cm)-re)<=ep) and (mm+cm<r)) or ((ff+cf)/(mm+cm)-re>ep) then
begin
re:=(ff+cf)/(mm+cm); r:=mm+cm;
l:=k;
end;
end;
for i:=1 to l do dau[d[i]]:=true;
if l=0 then writeln('NONE')
else
for i:=1 to x do
if dau[i] then
writeln(i);
end;

begin
rf;
pr;
end.


#### Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

class component {
public:
long long f, m; int id;
component(): f(0), m(0), id(0) {};
component(long long f, long long m, int id): f(f), m(m), id(id) {}
bool operator < (const component & o) const {
return f * o.m > m * o.f;
}
};

component car;
vector<component> cpns;

int main() {
int f, m, n;
scanf("%d%d%d", &f, &m, &n);
car = component(f, m, 0);
for(int i = 1; i <= n; ++i) {
scanf("%d%d", &f, &m);
cpns.push_back(component(f, m, i));
}
sort(cpns.begin(), cpns.end());
vector<int> ans;
for(typeof(cpns.begin()) it = cpns.begin(); it != cpns.end(); ++it) {
if(*it < car) {
ans.push_back(it->id);
car.f += it->f;
car.m += it->m;
}
}
if(!ans.empty()) {
sort(ans.begin(), ans.end());
for(vector<int>::iterator it = ans.begin(); it != ans.end(); ++it)
printf("%d\n", *it);
} else puts("NONE");
return 0;
}


program sboost;
uses    math;
const   fi='';
type    part=record
f,m,order:longint;
rate:real;
end;
var     a:array[1..10001] of part;
f,m,n,d:longint;
aa:real;
res:array[1..10001] of longint;
procedure input;
var     inp:text;
i:longint;
begin
assign(inp,fi);
reset(inp);
for i:=1 to n do
begin
a[i].rate:=a[i].f/a[i].m;
a[i].order:=i;
end;
close(inp);
end;

procedure swap(i,j:longint);
var     t:part;
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;

procedure sort(l,r:longint);
var     i,j:longint;
p:real;
begin
if l>=r then exit;
p:=a[random(r-l+1)+l].rate;
i:=l;j:=r;
repeat
while a[i].rate>p do inc(i);
while a[j].rate<p do dec(j);
if i<=j then
begin
if i<j then swap(i,j);
inc(i);dec(j);
end;
until i>j;
sort(l,j);sort(i,r);

end;

procedure sort2(l,r:longint);
var     i,j,t:longint;
p:real;
begin
if l>=r then exit;
p:=a[res[random(r-l+1)+l]].order;
i:=l;j:=r;
repeat
while a[res[i]].order<p do inc(i);
while a[res[j]].order>p do dec(j);
if i<=j then
begin
if i<j then
begin
t:=res[i];
res[i]:=res[j];
res[j]:=t;
end;

inc(i);dec(j);
end;
until i>j;
sort2(l,j);sort2(i,r);

end;

procedure greedy;
var     i:longint;
begin
aa:=f/m;
d:=0;
for i:=1 to n do
begin
if (f+a[i].f)/(m+a[i].m)>aa then
begin
inc(d);
res[d]:=i;
f:=f+a[i].f;
m:=m+a[i].m;
aa:=f/m;
end;
end;
end;

procedure output;
var     i:longint;
begin
if d=0 then write('NONE')
else
begin
sort2(1,d);
for i:=1 to d do
writeln(a[res[i]].order);
end;
end;

begin
input;
sort(1,n);
greedy;
output;
end.


#### Code mẫu của RR

#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(long i=a; i<=b; i++)
#define FORD(i,a,b) for(long i=a; i>=b; i--)
#define F first
#define S second
#define MP make_pair
#define MAXN 10111
using namespace std;

pair<pair<double,long>,pair<long long,long long> > a[MAXN];
long long mm,ff,m[MAXN],f[MAXN];
long ok[MAXN],n;

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
scanf("%lld %lld %ld",&ff,&mm,&n);
FOR(i,1,n) {
scanf("%lld %lld",&a[i].S.F,&a[i].S.S);
a[i].F.F=a[i].S.F/a[i].S.S;
a[i].F.S=i;
}
sort(a+1,a+n+1);

FORD(i,n,1)
if (mm*(ff+a[i].S.F)>ff*(mm+a[i].S.S)) {
ok[a[i].F.S]=1;
mm+=a[i].S.S;
ff+=a[i].S.F;
}

long res=0;
FOR(i,1,n) res+=ok[i];
if (!res) {
printf("NONE\n");
return 0;
}
FOR(i,1,n) if (ok[i]) printf("%ld\n",i);
return 0;
}


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

void sort(int min,int max,double a[],int b[])
{
int i=min;
int j=max;
double r=a[(min+max)/2];
while(i<=j)
{
while(a[i]>r) i++;
while(a[j]<r) j--;
if(i<=j)
{
double temp=a[j];
a[j]=a[i];
a[i]=temp;
int tem=b[j];
b[j]=b[i];
b[i]=tem;
i++;
j--;
}
}
if(j>min)
sort(min,j,a,b);
if(i<max)
sort(i,max,a,b);
}
void sort1(int min,int max,int a[],int b[])
{
int i=min;
int j=max;
int r=b[(min+max)/2];
while(i<=j)
{
while(b[i]<r) i++;
while(b[j]>r) j--;
if(i<=j)
{
int temp=a[j];
a[j]=a[i];
a[i]=temp;
temp=b[j];
b[j]=b[i];
b[i]=temp;
i++;
j--;
}
}
if(j>min)
sort1(min,j,a,b);
if(i<max)
sort1(i,max,a,b);
}

main()
{
int m[10002],b[10002],c[10002],M,n,so;
long long f[10002],F;
double a[10002];
scanf("%lld %d %d",&F,&M,&n);
for(int i=1;i<=n;i++)
{
scanf("%lld %d",&f[i],&m[i]);
b[i]=i;
a[i]=f[i]*1./m[i];
}
//for(int i=1;i<=n;i++)
// printf("%lf %d    ",a[i],b[i]);
sort(1,n,a,b);
//for(int i=1;i<=n;i++)
// printf("%lf %d    ",a[i],b[i]);
int u=1,v=1;
int t=1;
while(t<=n)
{
if(F*m[b[t]]<f[b[t]]*M)
{
F=F+f[b[t]];
M=M+m[b[t]];
t++;
}
else break;
}
t--;
if(t==0) printf("NONE");
else
{
sort1(1,t,c,b);
for(int i=1;i<=t;i++)
printf("%d\n",b[i]);
}
//  getch();
}


#### Code mẫu của ll931110

{
ID: ll9311102
PROB: sboost
LANG: PASCAL
}

{\$N+}
program sboost;
const
input  = '';
output = '';
maxn = 13000;
maxv = 2 * 1e6;
eps = 1e-10;
var
fi,fo: text;
f,m,a: array[0..maxn] of extended;
res: extended;
n,cc: longint;

procedure openfile;
begin
assign(fi, input);  reset(fi);
assign(fo, output);  rewrite(fo);
end;

procedure closefile;
begin
close(fo);
close(fi);
end;

procedure init;
var
i: longint;
begin
for i := 1 to n do readln(fi, f[i], m[i]);
end;

function ok(x: extended): boolean;
var
i: longint;
tot: extended;
begin
for i := 0 to n do a[i] := f[i] - x * m[i];
tot := a[0];

for i := 1 to n do
if a[i] > 0 then tot := tot + a[i];

ok := (tot >= -eps);
end;

procedure solve;
var
inf,sup,med: extended;
begin
inf := f[0]/m[0];  res := inf;
sup := maxv;
while sup - inf > eps do
begin
med := (inf + sup)/2;
if ok(med) then
begin
res := med;  inf := med;
end
else sup := med;
end;
end;

procedure trace(x: extended);
var
i: longint;
begin
for i := 1 to n do a[i] := f[i] - x * m[i];
cc := 0;
for i := 1 to n do if a[i] > 0 then inc(cc);
end;

procedure printresult;
var
i: longint;
begin
trace(res);
if cc = 0 then writeln(fo, 'NONE') else
for i := 1 to n do if a[i] > 0 then writeln(fo, i);
end;

begin
openfile;
init;
solve;
printresult;
closefile;
end.