#include "festival.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const long long maxn = 2e5 + 10;
long long n, a;
struct coupon
{
long long cost, type, index;
coupon(){};
coupon(long long _cost, long long _type, long long _index)
{
cost = _cost;
type = _type;
index = _index;
}
};
bool cmp(coupon c1, coupon c2)
{
return (c1.cost < c2.cost);
}
vector < coupon > g[5];
vector < long long > sums;
long long dp[maxn];
long long getone(long long tokens)
{
long long l = 0, r = sums.size()-1, mid = 0, ans = 0;
while(l <= r)
{
mid = (l + r)/2;
if(sums[mid] <= tokens)
{
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
return ans;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
a = A;
n = P.size();
for (long long i = 0; i < n; ++ i)
{
g[T[i]].pb(coupon(P[i], T[i], i));
}
for (long long curr = 1; curr <= 4; ++ curr)
sort(g[curr].begin(), g[curr].end(), cmp);
sums.pb(0);
long long pre = 0;
for (auto &[c, t, i]: g[1])
{
pre += c;
sums.pb(pre);
}
vector < int > res;
long long tokens = a;
dp[0] = getone(tokens);
long long mx = 0, best = dp[0];
long long cnt = 0;
for (auto &[c, t, i]: g[2])
{
if(tokens < c)break;
cnt ++;
tokens -= c;
if(tokens < 1LL * 1e17)tokens *= 2;
/// cout << "@ " << cnt << " " << i << endl;
/// cout << tokens << " for the ones " << endl;
dp[cnt] = cnt + getone(tokens);
if(best < dp[cnt])
{
best = dp[cnt];
mx = cnt;
}
}
/// for (long long i = 0; i <= g[2].size(); ++ i)
/// cout << dp[i] << " ";
/// cout << endl;
/// cout << mx << " " << best << endl;
for (long long i = 1; i <= mx; ++ i)
res.pb(g[2][i-1].index);
for (long long i = 1; i <= best - mx; ++ i)
res.pb(g[1][i-1].index);
return res;
}
