#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <class T> using PQMax = priority_queue<T>;
template <class T> using PQMin = priority_queue<T, vector<T>, greater<T>>;
template <class T1, class T2>
void maximize(T1 &a, T2 b){
if (b > a) a = b;
}
template <class T1, class T2>
void minimize(T1 &a, T2 b){
if (b < a) a = b;
}
template <class T>
void read(T &number)
{
bool negative = false;
register int c;
number = 0;
c = getchar();
while (c != '-' && !isalnum(c)) c = getchar();
if (c=='-'){
negative = true;
c = getchar();
}
for (; (c>47 && c<58); c=getchar())
number = number *10 + c - 48;
if (negative)
number *= -1;
}
template <class T, class ...Ts>
void read(T &a, Ts& ... args){
read(a);
read(args...);
}
/*
struct Node
{
int node, len;
Node() {node = len = 0;}
Node(int node, int len) {this -> node = node, this -> len = len;}
};
typedef vector<Node> vg;
*/
#define fi first
#define se second
#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
#define REV(type, i, b, a) for(type i = (b); i >= (a); i--)
#define testBit(n, bit) (((n) >> (bit)) & 1)
#define flipBit(n, bit) ((n) ^ (1ll << (bit)))
#define cntBit(n) __builtin_popcount(n)
#define cntBitll(n) __builtin_popcountll(n)
#define log2(n) (31 - __builtin_clz(n))
#define log2ll(n) (63 - __builtin_clzll(n))
#define CURRENT_TIMESTAMP chrono::steady_clock::now().time_since_epoch().count()
#define randomize mt19937_64 mt(CURRENT_TIMESTAMP)
#define MAX 1000001
#define MOD 1000000007
#define oo 1'000'000'000'000'000'000ll
struct Coupon {
int idx; ll p, t;
Coupon() {idx = p = t = 0;}
Coupon(int idx, ll p, int t): idx(idx), p(p), t(t) {}
};
ll A; int n;
int P[MAX], T[MAX];
namespace Subtask123 {
vector<int> prices[3];
vector<int> solve() {
FOR(int, i, 1, n)
prices[T[i]].push_back(i);
FOR(int, type, 1, 2)
sort(prices[type].begin(), prices[type].end(), [](int i, int j){
return P[i] < P[j];
});
vector<int> answer;
int ptr[3] = {};
while (ptr[1] < prices[1].size() and ptr[2] < prices[2].size()) {
ll newA1 = A - P[prices[1][ptr[1]]],
newA2 = (A - P[prices[2][ptr[2]]]) * 2;
// cerr << prices[1][ptr[1]] << ' ' << prices[2][ptr[2]] << ' ' << newA1 << ' ' << newA2 << '\n';
if (newA1 < 0 and newA2 < 0) break;
if (newA2 >= newA1)
A = newA2, answer.push_back(prices[2][ptr[2]++]);
else
A = newA1, answer.push_back(prices[1][ptr[1]++]);
}
FOR(int, type, 1, 2)
while (A > 0 and ptr[type] < prices[type].size()) {
int i = prices[type][ptr[type]++];
if (A < P[i]) break;
answer.push_back(i); A = (A - P[i]) * type;
}
for (int &value: answer) value -= 1;
return answer;
}
}
namespace Subtask4 {
int f[71][71][71][71];
int cnt[4];
vector<Coupon> prices;
}
std::vector<int> max_coupons(int _A, std::vector<int> _P, std::vector<int> _T) {
A = _A;
n = _P.size();
FOR(int, i, 1, n) P[i] = _P[i-1], T[i] = _T[i-1];
// FOR(int, i, 1, n) cerr << P[i] << " \n"[i == n];
// FOR(int, i, 1, n) cerr << T[i] << " \n"[i == n];
return Subtask123::solve();
}
