#include <bits/stdc++.h>
#include <ranges>
using namespace std;
#ifdef LOCAL
#include "../../debug.h"
#else
#define debug(...) 42
#endif
namespace utils {
template <typename T>
bool chMax(T& target, const T& value) {
if (value > target) {
target = value;
return true;
}
return false;
}
template <typename T>
bool chMin(T& target, const T& value) {
if (value < target) {
target = value;
return true;
}
return false;
}
} // namespace utils
using namespace utils;
using ll = long long;
using ld = long double;
using mp = vector<vector<int>>;
const char el = '\n';
int memo[71][71][71][71];
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
using cp = pair<ll, int>;
vector<vector<cp>> coupons(5);
int N = P.size();
for (int i = 0; i < N; ++i) {
coupons[T[i]].emplace_back(P[i], i);
}
for (int i = 1; i <= 4; ++i) {
ranges::sort(coupons[i]);
debug(i, coupons[i]);
}
memset(memo, -1, sizeof(memo));
function<int(int, int, int, int, ll)> dp = [&](int a, int b, int c, int d, ll tk) {
int &ret = memo[a][b][c][d];
if (ret != -1) return ret;
ret = 0;
if (a + b + c + d == N or tk == 0) {
return ret;
}
if (a < (int)coupons[1].size() and coupons[1][a].first <= tk) {
ret = max(ret, dp(a + 1, b, c, d, tk - coupons[1][a].first) + 1);
}
if (b < (int)coupons[2].size() and coupons[2][b].first <= tk) {
ret = max(ret, dp(a, b + 1, c, d, (tk - coupons[2][b].first) * 2) + 1);
}
if (c < (int)coupons[3].size() and coupons[3][c].first <= tk) {
ret = max(ret, dp(a, b, c + 1, d, (tk - coupons[3][c].first) * 3) + 1);
}
if (d < (int)coupons[4].size() and coupons[4][d].first <= tk) {
ret = max(ret, dp(a, b, c, d + 1, (tk - coupons[4][d].first) * 4) + 1);
}
return ret;
};
int res = dp(0, 0, 0, 0, A);
debug(res);
vector<int> ans;
vector<int> p(5, 0);
ll tk = A;
while (true) {
int a = p[1], b = p[2], c = p[3], d = p[4];
if (a + b + c + d == N or tk == 0) break;
int best = 0;
int best_type = 0;
for (int i = 1; i <= 4; ++i) {
if (p[i] < (int)coupons[i].size() && coupons[i][p[i]].first <= tk) {
int new_value = 1 + dp(a + (i == 1), b + (i == 2), c + (i == 3), d + (i == 4), (tk - coupons[i][p[i]].first) * i);
if (new_value > best) {
best = new_value;
best_type = i;
}
}
}
if (best == 0) break;
ans.push_back(coupons[best_type][p[best_type]].second);
tk = (tk - coupons[best_type][p[best_type]].first) * best_type;
p[best_type]++;
debug(p[1], p[2], p[3], p[4], tk);
}
debug(ans);
return ans;
}
// int main() {
// max_coupons(13, {4, 500, 8, 14}, {1, 3, 3, 4});
// return 0;
// }
