#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int n;
vector<vector<pii > > v;
vector<int> sz;
int appl(int money, int p_, int t_) {
return min((int) 1e17, (money - p_) * t_);
}
vector<signed> max_coupons(signed A, vector<signed> P, vector<signed> T) {
n = P.size();
v.resize(5);
sz.assign(5, 0);
for(int i = 0; i < n; i++) {
v[T[i]].pb(mp(P[i], i));
}
for(int i = 1; i <= 4; i++) {
sort(v[i].begin(), v[i].end());
sz[i] = v[i].size();
}
vector<vector<vector<vector<pii > > > > dp(1 + sz[1], vector<vector<vector<pii > > > (1 + sz[2], vector<vector<pii > > (1 + sz[3], vector<pii > (1 + sz[4], mp(-1, -1)))));
//vector<vector<vector<vector<int> > > > from(1 + sz[1], vector<vector<vector<int> > > (1 + sz[2], vector<vector<int> > (1 + sz[3], vector<int> (1 + sz[4], 0))));
dp[0][0][0][0] = mp(A, -1);
pair<int, vector<int> > best = mp(0, vector<int> {0, 0, 0, 0, 0});
for(int x1 = 0; x1 <= sz[1]; x1++) {
for(int x2 = 0; x2 <= sz[2]; x2++) {
for(int x3 = 0; x3 <= sz[3]; x3++) {
for(int x4 = 0; x4 <= sz[4]; x4++) {
if(x1 > 0 && dp[x1 - 1][x2][x3][x4].fi >= v[1][x1 - 1].fi) {
dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], mp(appl(dp[x1 - 1][x2][x3][x4].fi, v[1][x1 - 1].fi, 1), 1ll));
}
if(x2 > 0 && dp[x1][x2 - 1][x3][x4].fi >= v[2][x2 - 1].fi) {
dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], mp(appl(dp[x1][x2 - 1][x3][x4].fi, v[2][x2 - 1].fi, 2), 2ll));
}
if(x3 > 0 && dp[x1][x2][x3 - 1][x4].fi >= v[3][x3 - 1].fi) {
dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], mp(appl(dp[x1][x2][x3 - 1][x4].fi, v[3][x3 - 1].fi, 3), 3ll));
}
if(x4 > 0 && dp[x1][x2][x3][x4 - 1].fi >= v[4][x4 - 1].fi) {
dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], mp(appl(dp[x1][x2][x3][x4 - 1].fi, v[4][x4 - 1].fi, 4), 4ll));
}
if(dp[x1][x2][x3][x4].fi != -1) {
best = max(best, mp(x1 + x2 + x3 + x4, vector<int> {0, x1, x2, x3, x4}));
}
}
}
}
}
vector<signed> ans;
while(best.fi != 0) {
best.fi--;
int which = dp[best.se[1]][best.se[2]][best.se[3]][best.se[4]].se;
ans.pb(v[which][best.se[which] - 1].se);
best.se[which]--;
}
reverse(ans.begin(), ans.end());
return ans;
}
