#include "festival.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<ll,ll> pll;
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;
if (a == 1 || b == 1) return b == 1;
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];
ll sum = 0;
for (int i=0; i<n; i++){
a[i] = {P[i], T[i], i};
max_t = max(max_t, T[i]);
sum += P[i];
}
sort(a, a+n, comp);
vector<int> vans;
if (max_t <= 0){
int ini = 0;
while (ini < n && a[ini].t == 2) ini++;
int best = -1, ans = -1;
int m = n-ini+1;
ll pr[m];
pr[0] = 0;
for (int i=ini; i<n; i++){
pr[i-ini+1] = pr[i-ini] + a[i].p;
if (pr[i-ini+1] <= A) ans = i-ini+1;
}
ll aux = A;
bool todo = false;
for (int i=0; i<ini; i++){
// cout << a[i].p << " " << a[i].t << " " << a[i].id << "\n";
if (A < a[i].p) break;
if (A >= sum){
todo = true;
break;
}
A = 2*(A - a[i].p);
int r = upper_bound(pr, pr+m, A) - pr;
int val = (i+1) + (r-1);
if (ans <= val) ans = val, best = i;
}
A = aux;
// cout << "best_i : " << best_i << "\n";
// cout << "ans : " << ans << "\n";
if (todo){
for (int i=0; i<n; i++)
vans.push_back(a[i].id);
return vans;
}
for (int i=0; i<=best; i++){
A = 2*(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;
}
else if (n <= 70){
vector<int> pos[5];
for (int i=0; i<n; i++)
pos[a[i].t].push_back(i);
ll aux = A;
for (int i2=0; i2<=sz(pos[2]); i2++)
for (int i3=0; i3<=sz(pos[3]); i3++)
for (int i4=0; i4<=sz(pos[4]); i4++){
int vis[n] = {0};
for (int i=0; i<i2; i++)
vis[pos[2][i]] = true;
for (int i=0; i<i3; i++)
vis[pos[3][i]] = true;
for (int i=0; i<i4; i++)
vis[pos[4][i]] = true;
for (int i : pos[1])
vis[i] = true;
vector<int> vec;
A = aux;
for (int i=0; i<n; i++){
if (!vis[i]) continue;
A = a[i].t*(A - a[i].p);
if (A < 0) break;
if (A >= sum){
for (; i<n; i++)
if (vis[i])
vec.push_back(a[i].id);
break;
}
vec.push_back(a[i].id);
}
if (vans.size() < vec.size())
vans = vec;
}
return vans;
}
for (int i=0; i<n; i++)
vans.push_back(a[i].id);
return vans;
}
