#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
vector<array<long long, 2> > coupons[5];
coupons[1].push_back({0LL, 0LL});
coupons[2].push_back({0LL, 0LL});
coupons[3].push_back({0LL, 0LL});
coupons[4].push_back({0LL, 0LL});
int n = P.size();
for(int i = 0; i < n; i++) {
coupons[T[i]].push_back({P[i], i});
}
sort(coupons[1].begin(), coupons[1].end());
sort(coupons[2].begin(), coupons[2].end());
sort(coupons[3].begin(), coupons[3].end());
sort(coupons[4].begin(), coupons[4].end());
long long one_siz = coupons[1].size();
long long two_siz = coupons[2].size();
long long three_siz = coupons[3].size();
long long four_siz = coupons[4].size();
long long dp[one_siz][two_siz][three_siz][four_siz];
long long par[one_siz][two_siz][three_siz][four_siz];
for(long long i = 0; i < one_siz; i++) {
for(long long j = 0; j < two_siz; j++) {
for(long long k = 0; k < three_siz; k++) {
for(long long l = 0; l < four_siz; l++) {
dp[i][j][k][l] = -1;
par[i][j][k][l] = -1;
}
}
}
}
dp[0][0][0][0] = A;
for(long long i = 0; i < one_siz; i++) {
for(long long j = 0; j < two_siz; j++) {
for(long long k = 0; k < three_siz; k++) {
for(long long l = 0; l < four_siz; l++) {
if(i != 0) {
dp[i][j][k][l] = max(dp[i][j][k][l], (dp[i - 1][j][k][l] - coupons[1][i][0]) * 1LL);
}
if(j != 0) {
dp[i][j][k][l] = max(dp[i][j][k][l], (dp[i][j - 1][k][l] - coupons[2][j][0]) * 2LL);
}
if(k != 0) {
dp[i][j][k][l] = max(dp[i][j][k][l], (dp[i][j][k - 1][l] - coupons[3][k][0]) * 3LL);
}
if(l != 0) {
dp[i][j][k][l] = max(dp[i][j][k][l], (dp[i][j][k][l - 1] - coupons[4][l][0]) * 4LL);
}
if(dp[i][j][k][l] == (dp[i - 1][j][k][l] - coupons[1][i][0]) * 1LL) {
par[i][j][k][l] = 1;
}
else if(dp[i][j][k][l] == (dp[i][j - 1][k][l] - coupons[2][j][0]) * 2LL) {
par[i][j][k][l] = 2;
}
else if(dp[i][j][k][l] == (dp[i][j][k - 1][l] - coupons[3][k][0]) * 3LL) {
par[i][j][k][l] = 3;
}
else if(dp[i][j][k][l] == (dp[i][j][k][l - 1] - coupons[4][l][0]) * 4LL) {
par[i][j][k][l] = 4;
}
if(dp[i][j][k][l] > 1'000'000'000'000'000'000LL) {
dp[i][j][k][k] = 1'000'000'000'000'000'000LL;
}
}
}
}
}
long long ii = 0, jj = 0, kk = 0, ll = 0;
long long cur_val = A;
for(long long i = 0; i < one_siz; i++) {
for(long long j = 0; j < two_siz; j++) {
for(long long k = 0; k < three_siz; k++) {
for(long long l = 0; l < four_siz; l++) {
if(ii + jj + kk + ll < i + j + k + l && dp[i][j][k][l] != -1) {
ii = i;
jj = j;
kk = k;
ll = l;
cur_val = dp[i][j][k][l];
}
else if(ii + jj + kk + ll == i + j + k + l && dp[i][j][k][l] > cur_val) {
ii = i;
jj = j;
kk = k;
ll = l;
cur_val = dp[i][j][k][l];
}
}
}
}
}
vector<int> ans;
while(ii != 0 || jj != 0 || kk != 0 || ll != 0) {
if(par[ii][jj][kk][ll] == 1) {
ans.push_back(coupons[1][ii][1]);
ii--;
continue;
}
if(par[ii][jj][kk][ll] == 2) {
ans.push_back(coupons[2][jj][1]);
jj--;
continue;
}
if(par[ii][jj][kk][ll] == 3) {
ans.push_back(coupons[3][kk][1]);
kk--;
continue;
}
if(par[ii][jj][kk][ll] == 4) {
ans.push_back(coupons[4][ll][1]);
ll--;
continue;
}
}
reverse(ans.begin(), ans.end());
return ans;
}
