#include "festival.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
template<class T>bool minimize(T& a, T b){
if(a > b){
a = b;
return true;
}
return false;
}
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
return true;
}
return false;
}
int n;
ll A;
vector<int>p, t;
namespace sub1{
vector<int>solve(){
vector<int>R(n), ans;
iota(R.begin(), R.end(), 0);
sort(R.begin(), R.end(), [&] (int i, int j){
return p[i] < p[j];
});
for(int& i : R){
if((A -= p[i]) < 0){
break;
}
ans.push_back(i);
}
return ans;
}
}
namespace sub23{
vector<int>solve(){
vector<vector<int>>part(2);
for(int i = 0; i < n; i++){
part[t[i] - 1].push_back(i);
}
for(int i = 0; i < 2; i++){
sort(part[i].begin(), part[i].end(), [&] (int x, int y){
return p[x] < p[y];
});
}
vector<ll>f(1, 0);
for(int& i : part[0]){
f.push_back(f.back() + p[i]);
}
f[0] = -1;
function<int(ll)>calc = [&] (ll x){
return upper_bound(f.begin(), f.end(), x) - f.begin() - 1;
};
int best = calc(A), cnt_2 = 0;
for(int i = 0; i < part[1].size(); i++){
if(A < p[part[1][i]]){
break;
}
if(maximize(best, i + 1 + calc(A = min((A - p[part[1][i]]) << 1LL, INF)))){
cnt_2 = i + 1;
}
}
vector<int>ans(part[1].begin(), part[1].begin() + cnt_2);
for(int i = 0; i < best - cnt_2; i++){
ans.push_back(part[0][i]);
}
return ans;
}
}
namespace sub4{
ll dp[71][71][71][71];
short trace[71][71][71][71];
vector<int>solve(){
vector<vector<int>>part(5);
for(int i = 0; i < n; i++){
part[t[i]].push_back(i);
}
for(int i = 1; i < 5; i++){
sort(part[i].begin(), part[i].end(), [&] (int x, int y){
return p[x] < p[y];
});
}
memset(dp, -0x0f, sizeof(dp));
dp[0][0][0][0] = A;
vector<int>N;
int best = 0;
for(int n1 = 0; n1 <= part[1].size(); n1++){
for(int n2 = 0; n2 <= part[2].size(); n2++){
for(int n3 = 0; n3 <= part[3].size(); n3++){
for(int n4 = 0; n4 <= part[4].size(); n4++){
ll x = dp[n1][n2][n3][n4];
if(x < 0){
continue;
}
minimize(x, INF);
if(maximize(best, n1 + n2 + n3 + n4)){
N = {-1, n1, n2, n3, n4};
}
if(n1 < part[1].size() && x >= p[part[1][n1]] && maximize(dp[n1 + 1][n2][n3][n4], x - p[part[1][n1]])){
trace[n1 + 1][n2][n3][n4] = 1;
}
if(n2 < part[2].size() && x >= p[part[2][n2]] && maximize(dp[n1][n2 + 1][n3][n4], (x - p[part[2][n2]]) << 1LL)){
trace[n1][n2 + 1][n3][n4] = 2;
}
if(n3 < part[3].size() && x >= p[part[3][n3]] && maximize(dp[n1][n2][n3 + 1][n4], (x - p[part[3][n3]]) * 3)){
trace[n1][n2][n3 + 1][n4] = 3;
}
if(n4 < part[4].size() && x >= p[part[4][n4]] && maximize(dp[n1][n2][n3][n4 + 1], (x - p[part[4][n4]]) << 2LL)){
trace[n1][n2][n3][n4 + 1] = 4;
}
}
}
}
}
vector<int>ans;
for(int i = 0; i < best; i++){
int x = trace[N[1]][N[2]][N[3]][N[4]];
ans.push_back(part[x][N[x] - 1]);
N[x]--;
}
reverse(ans.begin(), ans.end());
return ans;
}
}
namespace sub5{
bool check_subtask(){
vector<int>idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&] (int x, int y){
return ll(p[x]) * t[x] * t[y] + ll(p[y]) * t[y] < ll(p[y]) * t[x] * t[y] + ll(p[x]) * t[x];
});
ll x = A;
for(int& i : idx){
if(x < p[i]){
return false;
}
x = min((x - p[i]) * t[i], INF);
}
return true;
}
vector<int>solve(){
vector<int>idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&] (int x, int y){
return ll(p[x]) * t[x] * t[y] + ll(p[y]) * t[y] < ll(p[y]) * t[x] * t[y] + ll(p[x]) * t[x];
});
return idx;
}
}
namespace sub6{
bool check_subtask(){
for(int i = 0; i < n; i++){
if((A - p[i]) * t[i] >= A){
return false;
}
}
return true;
}
vector<int>solve(){
vector<int>idx, other;
for(int i = 0; i < n; i++){
if(t[i] > 1){
idx.push_back(i);
}
else{
other.push_back(i);
}
}
sort(other.begin(), other.end(), [&] (int x, int y){
return p[x] < p[y];
});
vector<ll>f(1, 0);
for(int& i : other){
f.push_back(f.back() + p[i]);
}
f[0] = -1;
function<int(ll)>calc = [&] (ll x){
return upper_bound(f.begin(), f.end(), x) - f.begin() - 1;
};
sort(idx.begin(), idx.end(), [&] (int x, int y){
return ll(p[x]) * t[x] * t[y] + ll(p[y]) * t[y] < ll(p[y]) * t[x] * t[y] + ll(p[x]) * t[x];
});
vector<vector<ll>>dp(idx.size() + 1, vector<ll>(36, -INF));
vector<vector<bool>>trace(idx.size() + 1, vector<bool>(20, false));
dp[0][0] = A;
for(int i = 0; i < idx.size(); i++){
for(int j = 0; j < 36; j++){
ll x = dp[i][j];
if(maximize(dp[i + 1][j], x)){
trace[i + 1][j] = false;
}
if(j < 35 && x >= p[idx[i]] && maximize(dp[i + 1][j + 1], (x - p[idx[i]]) * t[idx[i]])){
trace[i + 1][j + 1] = true;
}
}
}
int best_n1 = 0, best = -1;
for(int i = 0; i < 36; i++){
if(dp[idx.size()][i] > -1 && maximize(best, i + calc(dp[idx.size()][i]))){
best_n1 = i;
}
}
vector<int>ans;
for(int i = idx.size(), j = best_n1; i > 0; i--){
if(trace[i][j]){
j--;
ans.push_back(idx[i - 1]);
}
}
reverse(ans.begin(), ans.end());
for(int i = 0; i < best - best_n1; i++){
ans.push_back(other[i]);
}
return ans;
}
}
namespace sub7{
vector<int>solve(){
vector<int>idx, other;
for(int i = 0; i < n; i++){
if(t[i] > 1){
idx.push_back(i);
}
else{
other.push_back(i);
}
}
sort(other.begin(), other.end(), [&] (int x, int y){
return p[x] < p[y];
});
vector<ll>f(1, 0);
for(int& i : other){
f.push_back(f.back() + p[i]);
}
f[0] = -1;
function<int(ll)>calc = [&] (ll x){
return upper_bound(f.begin(), f.end(), x) - f.begin() - 1;
};
sort(idx.begin(), idx.end(), [&] (int x, int y){
return ll(p[x]) * t[x] * t[y] + ll(p[y]) * t[y] < ll(p[y]) * t[x] * t[y] + ll(p[x]) * t[x];
});
vector<int>init_ans;
int pref = 0;
while(pref < idx.size()){
ll nA = (A - p[idx[pref]]) * t[idx[pref]];
if(nA < A){
break;
}
A = min(nA, INF);
init_ans.push_back(idx[pref++]);
}
int idx_sz = int(idx.size()) - pref;
vector<vector<ll>>dp(idx_sz + 1, vector<ll>(36, -INF));
vector<vector<bool>>trace(idx_sz + 1, vector<bool>(20, false));
dp[0][0] = A;
for(int i = 0; i < idx_sz; i++){
for(int j = 0; j < 36; j++){
ll x = dp[i][j];
if(maximize(dp[i + 1][j], x)){
trace[i + 1][j] = false;
}
if(j < 35 && x >= p[idx[i + pref]] && maximize(dp[i + 1][j + 1], (x - p[idx[i + pref]]) * t[idx[i + pref]])){
trace[i + 1][j + 1] = true;
}
}
}
int best_n1 = 0, best = -1;
for(int i = 0; i < 36; i++){
if(dp[idx_sz][i] > -1 && maximize(best, i + calc(dp[idx_sz][i]))){
best_n1 = i;
}
}
vector<int>ans;
for(int i = idx_sz, j = best_n1; i > 0; i--){
if(trace[i][j]){
j--;
ans.push_back(idx[i + pref - 1]);
}
}
reverse(ans.begin(), ans.end());
ans.insert(ans.begin(), init_ans.begin(), init_ans.end());
for(int i = 0; i < best - best_n1; i++){
ans.push_back(other[i]);
}
return ans;
}
}
vector<int>max_coupons(int _A, vector<int>_P, vector<int>_T){
A = _A;
swap(p, _P);
swap(t, _T);
n = p.size();
if(*max_element(t.begin(), t.end()) == 1){
return sub1::solve();
}
if(*max_element(t.begin(), t.end()) <= 2){
return sub23::solve();
}
if(n <= 70){
return sub4::solve();
}
if(sub5::check_subtask()){
return sub5::solve();
}
return sub6::check_subtask() ? sub6::solve() : sub7::solve();
}
