#include "festival.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct coupon{
ll p,t,id;
};
bool comp(coupon A,coupon B){ // *{P[i], T[i]}
auto [p, a, ida] = A;
auto [q, b, idb] = B;
if (a == b) return p <= q;
return a*b*p + b*q <= a*b*q + a*p;
}
vector<int> max_coupons(int _A,vector<int> P,vector<int> T){
int n = P.size(), max_t = 0;
ll A = _A;
coupon a[n];
for (int i=0; i<n; i++){
a[i] = {P[i], T[i], i};
max_t = max(max_t, T[i]);
}
sort(a, a+n, comp);
vector<int> vans;
if (max_t <= 2){
int ini = 0;
while (ini < n && a[ini].t == 2) ini++;
int best_i = -1, ans = 0, r = n-1;
ll acum = 0;
for (int i=ini; i<n; i++)
acum += a[i].p;
ll aux = A;
for (int i=0; i<ini; i++){
// cout << a[i].p << " " << a[i].t << " " << a[i].id << "\n";
if (A < a[i].p) break;
A = a[i].t*(A - a[i].p);
while (A < acum) acum -= a[r--].p;
int val = (i+1) + (r-ini+1);
if (ans < val) ans = val, best_i = i;
}
A = aux;
// cout << "best_i : " << best_i << "\n";
// cout << "ans : " << ans << "\n";
for (int i=0; i<=best_i; i++){
A = a[i].t*(A - a[i].p);
vans.push_back(a[i].id);
}
for (int i=ini; i<n; i++){
if (A < a[i].p) break;
A -= a[i].p;
vans.push_back(a[i].id);
}
return vans;
}
for (int i=0; i<n; i++)
vans.push_back(a[i].id);
return vans;
}
