#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;
const ll inf = ll(1e18);
const int maxN = int(2e5)+7;
int w; vector<int> p , t;
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;
}
namespace sub1{
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 S[maxN];
int calc(ll x){
int l = 0 , r = sz(g[0]) , ans = 0;
while (l <= r){
int mid = (l + r) / 2;
if (x >= S[mid]){
ans = mid;
l = mid + 1;
}
else{
r = mid - 1;
}
}
return ans;
}
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]));
S[0] = 0;
for (int i = 0 ; i < sz(g[0]) ; i++){
S[i + 1] = S[i] + 1ll * g[0][i].fi;
}
pair<int , int> res = {calc(w) , 0};
ll cur = w;
for (int i = 0 ; i < sz(g[1]) ; i++){
if (cur > g[1][i].fi){
cur = cost(cur , g[1][i].se);
if (res.fi < i + 1 + calc(cur)){
res = {i + 1 + calc(cur) , i + 1};
}
}
}
vector<int> ans;
for (int i = 0 ; i < res.se ; i++) ans.push_back(g[1][i].se);
for (int i = 0 ; i < res.fi - res.se ; i++) ans.push_back(g[0][i].se);
return ans;
}
}
namespace sub5{
vector<ii> g[4];
int id[4];
ll S[maxN];
int calc(ll x){
int l = 0 , r = sz(g[0]) , ans = 0;
while (l <= r){
int mid = (l + r) / 2;
if (x >= S[mid]){
ans = mid;
l = mid + 1;
}
else{
r = mid - 1;
}
}
return ans;
}
vector<int> solve(){
int n = sz(p);
for (int i = 0 ; i < n ; i++){
g[t[i] - 1].push_back({p[i] , i});
}
for (int i = 0 ; i < 4 ; i++){
sort(all(g[i]));
id[i] = 0;
}
S[0] = 0;
for (int i = 0 ; i < sz(g[0]) ; i++){
S[i + 1] = S[i] + 1ll * g[0][i].fi;
}
pair<int , int> res = {calc(w) , 0};
vector<int> tmp_lis;
ll cur = w;
while (true){
vector<int> tmp;
for (int i = 1 ; i < 4 ; i++){
if (id[i] < sz(g[i])){
if (cur <= cost(cur , g[i][id[i]].se)) tmp.push_back(i);
}
}
if (tmp.empty()) break;
for (int i = 0 ; i < sz(tmp) ; i++){
for (int j = i + 1 ; j < sz(tmp) ; j++){
ll X = 1ll * (tmp[i] + 1) * tmp[j] * g[tmp[i]][id[tmp[i]]].fi;
ll Y = 1ll * tmp[i] * (tmp[j] + 1) * g[tmp[j]][id[tmp[j]]].fi;
if (Y <= X) swap(tmp[i] , tmp[j]);
}
}
int pos = g[tmp[0]][id[tmp[0]]].se;
cur = cost(cur , pos);
tmp_lis.push_back(pos);
id[tmp[0]]++;
int X = calc(cur);
if (X + sz(tmp_lis) > res.fi){
res = {X + sz(tmp_lis) , sz(tmp_lis)};
}
}
while (true){
vector<int> tmp;
for (int i = 1 ; i < 4 ; i++){
if (id[i] < sz(g[i])){
if (cur >= g[i][id[i]].fi) tmp.push_back(i);
}
}
if (tmp.empty()) break;
for (int i = 0 ; i < sz(tmp) ; i++){
for (int j = i + 1 ; j < sz(tmp) ; j++){
ll X = 1ll * (tmp[i] + 1) * tmp[j] * g[tmp[i]][id[tmp[i]]].fi;
ll Y = 1ll * tmp[i] * (tmp[j] + 1) * g[tmp[j]][id[tmp[j]]].fi;
if (Y <= X) swap(tmp[i] , tmp[j]);
}
}
int pos = g[tmp[0]][id[tmp[0]]].se;
cur = cost(cur , pos);
tmp_lis.push_back(pos);
id[tmp[0]]++;
int X = calc(cur);
if (X + sz(tmp_lis) > res.fi){
res = {X + sz(tmp_lis) , sz(tmp_lis)};
}
}
vector<int> ans;
for (int i = 0 ; i < res.se ; i++) ans.push_back(tmp_lis[i]);
for (int i = 0 ; i < res.fi - res.se ; i++) ans.push_back(g[0][i].se);
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 sub5::solve();
}
// 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);
// cout << sz(ans) << "\n";
// //for (int x : ans) cout << x << " ";
// //cerr << sz(ans) << " " << n << "\n";
// return 0;
// }
