#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
// editorial
int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
int n = (int) a.size();
vector<pair<int, int>> c(n);
for (int i = 0; i < n; i++) {
c[i] = make_pair(a[i], b[i]);
}
sort(c.begin(), c.end());
vector<vector<int>> dp(n + 1, vector<int>(x + 1, -1));
dp[0][x] = y;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= x; j++) {
if (dp[i][j] == -1) {
continue;
}
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - c[i].second);
if (j - c[i].first >= 0) {
dp[i + 1][j - c[i].first] = max(dp[i + 1][j - c[i].first], dp[i][j]);
}
}
}
int ans = 0;
vector<int> d;
for (int i = n; i >= 0; i--) {
if (i < n) {
d.emplace_back(c[i].second);
sort(d.begin(), d.end());
}
vector<int> pref(d.size() + 1);
for (int j = 0; j < (int) d.size(); j++) {
pref[j + 1] = pref[j] + d[j];
}
for (int j = 0; j <= x; j++) {
if (dp[i][j] == -1) {
continue;
}
int k = (int) (upper_bound(pref.begin(), pref.end(), dp[i][j]) - pref.begin() - 1);
ans = max(ans, i + k);
}
}
return ans;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << find_maximum_unique(2, 3, {2, 1, 4}, {2, 3, 2}) << '\n';
cout << find_maximum_unique(6, 12, {5, 1, 5, 6, 3}, {3, 5, 4, 6, 7}) << '\n';
return 0;
}
#endif
