#include "festival.h"
#include <bits/stdc++.h>
#define int long long
#define all(a) begin(a), end(a)
using namespace std;
const int MX = 2e14 + 11;
struct coupon {
int p, t, id;
bool operator< (const coupon& o) const {
return p < o.p;
}
int apply(int x) {
return max(-1LL, min(MX, (x - p) * t));
}
};
vector<coupon> C[5];
#define forn(i, n) for (int i = 0; i < (int) (n); i++)
vector<int32_t> max_coupons(int32_t A, vector<int32_t> P, vector<int32_t> T) {
for (int i = 0; i < P.size(); i++) {
C[T[i]].push_back({P[i], T[i], i});
}
for (int t = 1; t <= 4; t++) {
sort(C[t].begin(), C[t].end());
}
vector<int32_t> ans;
vector<int> ps {0};
for (int i = 0; i < C[1].size(); i++) {
ps.push_back(ps.back() + C[1][i].p);
}
int X = A;
vector<int> K;
for (int c2 = 0; c2 <= C[2].size(); c2++) {
int c1 = upper_bound(all(ps), X) - ps.begin() - 1;
if (c1 >= 0 && c1 + c2 > accumulate(all(K), 0LL))
K = {c1, c2};
if (c2 < C[2].size()) X = C[2][c2].apply(X);
}
for (int i = 0; i < K[1]; i++) ans.push_back(C[2][i].id);
for (int i = 0; i < K[0]; i++) ans.push_back(C[1][i].id);
return ans;
}
