#include "festival.h" #include <bits/stdc++.h> #define all(V) V.begin(), V.end() #define rall(V) V.rbegin(), V.rend() using namespace std; #define ll long long struct cp { ll p, id; bool operator<(const cp &o) const { return p < o.p; } }; bool cmp(cp a, cp b) { return a.p < b.p; } vector<deque<cp>> V; int N; ll X; ll stop = -1; vector<int> ord; ll ansmax = 0; ll t = 0; ll scegli1 = 0; vector<ll> p1; vector<ll> cesti1; std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) { V = vector(5, deque<cp>()); N = P.size(); X = A; for(int i=0; i<N; i++) { V[T[i]].push_back({P[i], i}); } for(int i=0; i<5; i++) sort(all(V[i])); ll p = 0; for(int i=0; i<V[1].size(); i++) { p += V[1][i].p; p1.push_back(p); cesti1.push_back(V[1][i].id); } cp search = {X, -1}; ansmax = scegli1 = upper_bound(all(p1), X) - p1.begin(); while(1) { fprintf(stderr, "==============\nansmax=%lld, t=%lld, scegli1=%lld\n", ansmax, t, scegli1); ll a, b, c; a = b = c = stop; if(!V[2].empty()) a = V[2].front().p; if(!V[3].empty()) b = V[3].front().p; if(!V[4].empty()) c = V[4].front().p; if(a > X) a = stop; if(b > X) b = stop; if(c > X) c = stop; if(a == stop && b == stop && c == stop) break; if((4*a <= 3*b || b == stop) && (6*a <= 4*c || c == stop) && a != stop) { if(a == stop) exit(1); ord.push_back(V[2][0].id); V[2].pop_front(); X -= a; X *= 2; } else if((9*b <= 8*c || c == stop) && b != stop) { if(b == stop) exit(1); ord.push_back(V[3][0].id); V[3].pop_front(); X -= b; X *= 3; } else { if(c == stop) exit(1); ord.push_back(V[4][0].id); V[4].pop_front(); X -= c; X *= 4; } fprintf(stderr, "X = %lld\n", X); search = {X, -1}; ll ac1 = upper_bound(all(p1), X) - p1.begin(); fprintf(stderr, "ac1 = %lld\n", ac1); if(ord.size() + ac1 > ansmax) { ansmax = ord.size() + ac1; t = ord.size(); scegli1 = ac1; } } fprintf(stderr, "\n"); ll ac1 = upper_bound(all(p1), X) - p1.begin(); fprintf(stderr, "ac1 = %lld\n", ac1); if(ord.size() + ac1 > ansmax) { ansmax = ord.size() + ac1; t = ord.size(); scegli1 = ac1; } vector<int> ans; for(int i=0; i<t; i++) ans.push_back(ord[i]); for(int i=0; i<scegli1; i++) ans.push_back(cesti1[i]); return ans; } /* 10 9 1 1 1 1 1 1 1 1 4 2 1 1 1 1 1 1 1 1 1 1 */ #ifdef MARCO int main() { int N, A; assert(2 == scanf("%d %d", &N, &A)); std::vector<int> P(N), T(N); for (int i = 0; i < N; i++) assert(2 == scanf("%d %d", &P[i], &T[i])); fclose(stdin); std::vector<int> R = max_coupons(A, P, T); int S = R.size(); printf("%d\n", S); for (int i = 0; i < S; i++) printf("%s%d", (i == 0 ? "" : " "), R[i]); printf("\n"); fclose(stdout); return 0; } #endif