#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 100100*2;
const ll MOD = 1e9+7;
const ll INF = 1e15;
struct Coupon {
ll p, t, n;
bool operator < (const Coupon& x) const {
if((t==1)^(x.t==1)) return x.t==1;
if(t==1) return p<x.p;
return p*t*(x.t-1) < x.p*x.t*(t-1);
}
} arr[MAXN];
vector<int> lst[5];
const int MAXM = 50;
ll dp[MAXM][MAXM][MAXM];
ll sum[MAXN];
vector<int> res, res1;
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
int n = P.size();
for(int i=0; i<n; i++) arr[i] = {P[i],T[i], i};
sort(arr, arr+n);
int idx=0; ll cur=A;
while(idx<n && cur<INF) {
if((cur-arr[idx].p)*arr[idx].t < cur) break;
res.push_back(idx);
cur = arr[idx].t*(cur-arr[idx].p); idx++;
}
if(cur>=INF) {
while(idx<n) res.push_back(idx++);
for(auto &x:res) x=arr[x].n;
return res;
}
for(int t=1;t<=4;t++) lst[t] = {-1};
for(int i=idx;i<n;i++) {
lst[arr[i].t].push_back(i);
}
int sz=lst[1].size();
for(int i=1; i<sz; i++) sum[i]=sum[i-1]+arr[lst[1][i]].p;
memset(dp, -1, sizeof dp);
pair<int, vector<int> > mx = make_pair(0, vector<int>{0});
for(int i=0;i<MAXM&&i<lst[2].size();i++) {
for(int j=0;j<MAXM&&j<lst[3].size();j++) {
for(int k=0;k<MAXM&&k<lst[4].size();k++) {
if(!i && !j && !k) {
dp[i][j][k] = cur;
} else {
int x = max(max(lst[2][i], lst[3][j]), lst[4][k]);
int di = (lst[2][i]==x), dj = (lst[3][j]==x), dk = (lst[4][k]==x);
if(dp[i-di][j-dj][k-dk] >= arr[x].p) {
dp[i][j][k] = arr[x].t*(dp[i-di][j-dj][k-dk]-arr[x].p);
}
}
if(dp[i][j][k] != -1) {
int it = upper_bound(sum, sum+sz, dp[i][j][k])-sum-1;
mx = max(mx, make_pair(i+j+k+it, vector<int>{i,j,k,it}));
}
}
}
}
vector<int> v=mx.ss;
for(int t=1;t<=v[0];t++) res.push_back(lst[2][t]);
for(int t=1;t<=v[1];t++) res.push_back(lst[3][t]);
for(int t=1;t<=v[2];t++) res.push_back(lst[4][t]);
for(int t=1;t<=v[3];t++) res.push_back(lst[1][t]);
sort(all(res));
for(auto &x:res) x=arr[x].n;
return res;
}
