#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];
int dp[71][71][71][71], prv[71][71][71][71];
#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());
}
forn (c1, C[1].size() + 1) forn (c2, C[2].size() + 1) forn (c3, C[3].size() + 1) forn (c4, C[4].size() + 1)
{
dp[c1][c2][c3][c4] = -1;
}
dp[0][0][0][0] = A;
forn (c1, C[1].size() + 1) forn (c2, C[2].size() + 1) forn (c3, C[3].size() + 1) forn (c4, C[4].size() + 1)
{
int& cur_val = dp[c1][c2][c3][c4];
int& prv_ptr = prv[c1][c2][c3][c4];
if (c1 > 0) {
int new_val = C[1][c1 - 1].apply(dp[c1 - 1][c2][c3][c4]);
if (new_val > cur_val) {
cur_val = new_val;
prv_ptr = 1;
}
}
if (c2 > 0) {
int new_val = C[2][c2 - 1].apply(dp[c1][c2 - 1][c3][c4]);
if (new_val > cur_val) {
cur_val = new_val;
prv_ptr = 2;
}
}
if (c3 > 0) {
int new_val = C[3][c3 - 1].apply(dp[c1][c2][c3 - 1][c4]);
if (new_val > cur_val) {
cur_val = new_val;
prv_ptr = 3;
}
}
if (c4 > 0) {
int new_val = C[4][c4 - 1].apply(dp[c1][c2][c3][c4 - 1]);
if (new_val > cur_val) {
cur_val = new_val;
prv_ptr = 4;
}
}
}
vector<int> correct;
forn (c1, C[1].size() + 1) forn (c2, C[2].size() + 1) forn (c3, C[3].size() + 1) forn (c4, C[4].size() + 1)
{
if (dp[c1][c2][c3][c4] >= 0 && c1 + c2 + c3 + c4 >= accumulate(all(correct), 0LL)) {
correct = {c1, c2, c3, c4};
}
}
// for (auto x : correct) cout << x << ' '; cout << endl;
vector<int32_t> ans;
while (accumulate(all(correct), 0LL) > 0) {
auto& K = correct;
int p = prv[K[0]][K[1]][K[2]][K[3]];
ans.push_back(C[p][--K[p - 1]].id);
}
reverse(all(ans));
return ans;
}
