#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
typedef long long ll;
using pi = pair<ll, ll>;
using vi = vector<ll>;
struct coupon {
ll t, p, idx;
ll eval(ll R) {
if (R < p) return 0;
return (R-p)*t;
}
const bool operator<(const coupon &other) const {
return t == other.t ? p < other.p : t < other.t;
}
};
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
ll a = A, n = P.size();
ll required = 0, one = 0, two = 0, three = 0, four = 0;
vector<coupon> coupons[5]; for (int i = 0; i < n; i++) {
coupons[T[i]].push_back(coupon{T[i], P[i], i}), required += P[i];
if (T[i] == 1) one++;
else if (T[i] == 2) two++;
else if (T[i] == 3) three++;
else four++;
}
for (int i = 1; i <= 4; i++) sort(all(coupons[i]));
vector<vector<int>> ways;
for (int t = 0; t <= two; t++) {
for (int o = 0; o <= three; o++) {
for (int f = 0; f <= four; f++) {
vector<vector<int>> v(3);
for (int i =0; i < t; i++) v[0].push_back(coupons[2][i].idx);
for (int i =0; i < o; i++) v[1].push_back(coupons[3][i].idx);
for (int i =0; i < f; i++) v[2].push_back(coupons[4][i].idx);
const int P[6][3] = {{0,1,2}, {0,2,1}, {1,0,2},{1,2,0},{2,0,1}, {2,1,0}};
for (int p = 0; p < 6; p++) {
ways.push_back(vector<int>());
for (auto el : v[P[p][0]]) ways.back().push_back(el);
for (auto el : v[P[p][1]]) ways.back().push_back(el);
for (auto el : v[P[p][2]]) ways.back().push_back(el);
}
}
}
}
vector<ll> pref1; for (int i = 0; i < coupons[1].size(); i++) {
if (i == 0) pref1.push_back(coupons[1][i].p);
else pref1.push_back(pref1.back() + coupons[1][i].p);
}
int best = 0, besta = 0, best1 = upper_bound(all(pref1), a) - pref1.begin();
for (int i = 0; i < ways.size(); i++) {
ll k = a, req = required;
bool works = true;
for (auto idx : ways[i]) {
ll p = P[idx];
if (k - p < 0) {works = false; break;}
if (k >= req) break;
k = (k-p) * T[idx];
req -= p;
}
if (!works) continue;
int t1 = upper_bound(all(pref1), k) - pref1.begin();
if (ways[i].size() + t1 >= besta+best1) {
best = i; besta = ways[i].size(); best1 = t1;
}
}
vector<int> ans; for (auto el : ways[best]) ans.push_back(el);
for (int i = 0; i < best1; i++) ans.push_back(coupons[1][i].idx);
return ans;
}
