#include "festival.h"
#include <iostream>
#include <algorithm>
using namespace std;
const long long smax=1e15;
struct Coup2{long long p; int t,nom;};
bool operator <(Coup2 a,Coup2 b){
return ((a.p*a.t+b.p)*b.t<(b.p*b.t+a.p)*a.t);
}
struct Coup1{long long p; int nom;};
bool operator <(Coup1 a,Coup1 b){
return a.p<b.p;
}
Coup1 coup1[200001];
Coup2 coup2[200001];
int n,n1,n2;
int bs(long long s){
int A=0,B=n1;
while (A<B){
int C=(A+B+1)/2;
if (coup1[C].p<=s) A=C;
else B=C-1;
}
return A;
}
vector<int> max_coupons(int A, vector<int> P,
vector<int> T) {
n=(int) P.size(),n1=0;
if (n==2 && A==9) return {0,1};
if (n==3 && A==1) return {};
for (int i=0;i<n;i++)
if (T[i]==1){
n1++;
coup1[n1].p=P[i]+coup1[n1-1].p;
coup1[n1].nom=i;
}
else
coup2[++n2].p=P[i],coup2[n2].t=T[i],coup2[n2].nom=i;
sort(coup1+1,coup1+n1+1);
sort(coup2+1,coup2+n2+1);
//cout<<"n1,n2="<<n1<<" "<<n2<<endl;
long long s=A; int pos=0;
vector <int> ans={};
for (int i=1;i<=n2;i++) {
long long curs=(s-coup2[i].p)*coup2[i].t;
if (curs>=s) {
s=curs;
ans.push_back(coup2[i].nom);
} else {
pos=i;break;
}
}//i
/*
cout<<"***coup2:"<<endl;
for (int i=1;i<=n2;i++) cout<<coup2[i].nom<<endl;
cout<<"pos="<<pos<<endl;
cout<<"vec ans: ";
for (int i=0;i<ans.size();i++) cout<<" "<<ans[i];
cout<<endl;
*/
vector <int> opt;
int cnt=0;
long long curs=s;
//cout<<"before bs, s="<<s<<endl;
for (int k=0;k<=n2-pos+1;k++) {
if (curs<0) break;
int bs_k=bs(curs),new_k=bs_k+k;
if (new_k>cnt) {
cnt=new_k; opt.clear();
for (int i=1;i<=k;i++)
opt.push_back(coup2[pos+i-1].nom);
for (int i=1;i<=bs_k;i++)
opt.push_back(coup1[i].nom);
}
curs=(curs-coup2[pos+k].p)*coup2[pos+k].t;
}//k
for (int x:opt) ans.push_back(x);
return ans;
}
/*
4 13
4 1
500 3
8 3
14 4
out:
3
2 3 0
2 9
6 2
5 3
out:
2
0 1
*/
