#include "festival.h"
#include <bits/stdc++.h>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int , int> ii;
int w; vector<int> p , t;
namespace sub1{
const int maxN = int(2e5)+7;
const ll inf = ll(1e18);
bool check(){
int n = sz(p);
for (int i = 0 ; i < n ; i++){
if (t[i] > 2) return false;
}
return true;
}
vector<ii> g[2];
ll cost(ll cur , int i){
ll tmp = cur - 1ll * p[i];
if (tmp <= inf / t[i]) return 1ll * tmp * t[i]; else return inf;
}
vector<int> solve(){
int n = sz(p);
for (int i = 0 ; i < n ; i++){
g[t[i] - 1].push_back({p[i] , i});
}
sort(all(g[0])); sort(all(g[1]));
ll cur = w;
int i = 0 , j = 0;
vector<int> ans;
while (i < sz(g[0]) && j < sz(g[1])){
if (cur >= max(g[0][i].fi , g[1][j].fi)){
ll X = cost(cur , g[0][i].se);
ll Y = cost(cur , g[1][j].se);
if (X > Y){
cur = X;
ans.push_back(g[0][i].se);
i++;
}
else{
cur = Y;
ans.push_back(g[1][j].se);
j++;
}
}
else{
break;
}
}
while (i < sz(g[0])){
if (cur >= g[0][i].fi){
cur = cost(cur , g[0][i].se);
ans.push_back(g[0][i].se);
i++;
}
else{
break;
}
}
while (j < sz(g[1])){
if (cur >= g[1][j].fi){
cur = cost(cur , g[1][j].se);
ans.push_back(g[1][j].se);
j++;
}
else{
break;
}
}
return ans;
}
}
vector<int> max_coupons(int W , vector<int> P , vector<int> T){
w = W; p = P; t = T;
if (sub1::check()) return sub1::solve();
return {};
}
// int main(){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("templete.inp" , "r" , stdin);
// freopen("templete.out" , "w" , stdout);
// int n , W; cin >> n >> W;
// vector<int> P(n) , T(n);
// for (int &x : P) cin >> x;
// for (int &x : T) cin >> x;
// vector<int> ans = max_coupons(W , P , T);
// for (int x : ans) cout << x << " ";
// return 0;
// }
