#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 2e16;
int n;
ll tot;
void dbg(int x) {
cout << "DEBUG: " << x << "\n";
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
n = P.size();
tot = A;
vector<vector<pair<ll, int>>> els(5);
for (int i = 1; i <= 4; i++) els[i].push_back({-1, -1});
for (int i = 0; i < n; i++) {
els[T[i]].push_back({P[i], i});
}
for (int i = 1; i <= 4; i++) sort(els[i].begin(), els[i].end());
int b = min(1000, (int)els[2].size() - 1);
int c = min(500, (int)els[3].size() - 1);
int d = min(250, (int)els[4].size() - 1);
vector<vector<vector<ll>>> dp(b+1, vector<vector<ll>>(c+1, vector<ll>(d+1, 0)));
vector<vector<vector<int>>> pp(b+1, vector<vector<int>>(c+1, vector<int>(d+1, 0)));
dp[0][0][0] = tot;
vector<int> cons;
int best = 0;
//for (int i = 0; i <= a; i++) {
for (int j = 0; j <= b; j++) {
for (int k = 0; k <= c; k++) {
for (int l = 0; l <= d; l++) {
if (j == 0 && k == 0 && l == 0) continue;
dp[j][k][l] = -INF;
/*
if (i > 0 && dp[i-1][j][k][l] > 0) {
dp[i][j][k][l] = max(dp[i][j][k][l], dp[i-1][j][k][l] - els[1][i].first);
pp[i][j][k][l] = 1;
}
*/
if (j > 0 && dp[j-1][k][l] > 0) {
ll v = 2 * dp[j-1][k][l] - 2 * els[2][j].first;
if (v >= dp[j][k][l]) {
pp[j][k][l] = 2;
dp[j][k][l] = v;
}
}
if (k > 0 && dp[j][k-1][l] > 0) {
ll v = 3 * dp[j][k-1][l] - 3 * els[3][k].first;
if (v >= dp[j][k][l]) {
pp[j][k][l] = 3;
dp[j][k][l] = v;
}
}
if (l > 0 && dp[j][k][l-1] > 0) {
ll v = 4 * dp[j][k][l-1] - 4 * els[4][l].first;
if (v >= dp[j][k][l]) {
pp[j][k][l] = 4;
dp[j][k][l] = v;
}
}
if (dp[j][k][l] > INF) {
dp[j][k][l] = INF;
}
if (dp[j][k][l] >= 0) {
if (j + k + l >= best) {
cons = {0, j, k, l};
best = j + k + l;
}
}
}
}
}
vector<int> ff = cons;
vector<int> ans;
while (cons[1] + cons[2] + cons[3] > 0) {
int j = cons[1];
int k = cons[2];
int l = cons[3];
if (pp[j][k][l] == 2) {
ans.push_back(els[2][j].second);
cons[1]--;
}
else if (pp[j][k][l] == 3) {
ans.push_back(els[3][k].second);
cons[2]--;
}
else if (pp[j][k][l] == 4) {
ans.push_back(els[4][l].second);
cons[3]--;
}
}
reverse(ans.begin(), ans.end());
cons = ff;
for (int i = cons[3]+1; i < (int)els[4].size(); i++) {
ans.push_back(els[4][i].second);
}
for (int i = cons[2]+1; i < (int)els[3].size(); i++) {
ans.push_back(els[3][i].second);
}
for (int i = cons[1]+1; i < (int)els[2].size(); i++) {
ans.push_back(els[2][i].second);
}
for (int i = cons[0]+1; i < (int)els[1].size(); i++) {
ans.push_back(els[1][i].second);
}
return ans;
}
