#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 72;
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
vector <pll> t[5];
ll dp[maxn][maxn][maxn][maxn];
const ll oo = (1e+16);
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T)
{
ll rA = A;
int N = P.size();
for(int i = 0; i < N ; i++)
{
t[T[i]].push_back({P[i],i});
}
for(int j = 1 ; j <= 4 ; j++)sort(t[j].begin() , t[j].end());
for(int i = 0 ; i <= t[1].size() ; i++)
for(int j = 0 ; j <= t[2].size() ; j++)
for(int k = 0 ; k <= t[3].size() ; k++)
for(int l = 0 ; l <= t[4].size() ; l++)
{
dp[i][j][k][l] = -1;
}
int res = 0 , indi = 0 , indj = 0 , indk = 0 ,indl = 0;
dp[0][0][0][0] = rA;
for(int i = 0 ; i <= t[1].size() ; i++)
{
for(int j = 0 ; j <= t[2].size() ; j++)
{
for(int k = 0 ; k <= t[3].size() ; k++)
{
for(int l = 0 ; l <= t[4].size() ; l++)
{
if(i != 0)dp[i][j][k][l] = max(dp[i][j][k][l] , (dp[i-1][j][k][l]-t[1][i-1].st)*1);
if(j != 0)dp[i][j][k][l] = max(dp[i][j][k][l] , (dp[i][j-1][k][l]-t[2][j-1].st)*2);
if(k != 0)dp[i][j][k][l] = max(dp[i][j][k][l] , (dp[i][j][k-1][l]-t[3][k-1].st)*3);
if(l != 0)dp[i][j][k][l] = max(dp[i][j][k][l] , (dp[i][j][k][l-1]-t[4][l-1].st)*4);
dp[i][j][k][l] = min(dp[i][j][k][l] , oo);
}
}
}
}
for(int i = 0 ; i <= t[1].size() ; i++)
{
for(int j = 0 ; j <= t[2].size() ; j++)
{
for(int k = 0 ; k <= t[3].size() ; k++)
{
for(int l = 0 ; l <= t[4].size() ; l++)
{
if(dp[i][j][k][l] >= 0 && i+j+k+l > res)
{
res = i+j+k+l;
indi = i;
indj = j;
indk = k;
indl = l;
}
}
}
}
}
vector <int> K;
int i = indi , j = indj , k = indk , l = indl;
while(i != 0 || j != 0 || k != 0 || l != 0)
{
if(i != 0 && dp[i][j][k][l] == min(oo,(dp[i-1][j][k][l]-t[1][i-1].st)*1))
{
K.push_back(t[1][i-1].nd); i--;
}
else if(j != 0 && dp[i][j][k][l] == min(oo,(dp[i][j-1][k][l]-t[2][j-1].st)*2))
{
K.push_back(t[2][j-1].nd); j--;
}
else if(k != 0 && dp[i][j][k][l] == min(oo,(dp[i][j][k-1][l]-t[3][k-1].st)*3))
{
K.push_back(t[3][k-1].nd); k--;
}
else if(l != 0 && dp[i][j][k][l] == min(oo,(dp[i][j][k][l-1]-t[4][l-1].st)*4))
{
K.push_back(t[4][l-1].nd);
l--;
}
}
reverse(K.begin() , K.end());
return {K};
}
