#include <algorithm>
#include <cassert>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <tuple>
typedef std::vector<int> Vec;
typedef std::pair<int, int> Pii;
#define rep(i,a,b) for(auto i = a; i != b; ++i)
const int MN = 2e3+10;
const int MV = 1e4+10;
struct Data {
public:
int jelly_count, remain_b;
Data(int cnt, int rem): jelly_count(cnt), remain_b(rem) {}
Data increase_jelly_count() {return {jelly_count+1, remain_b};}
Data buy_b(int cost) { return {jelly_count+1, remain_b - cost};}
bool operator < (const Data& o) const {
return std::tie(jelly_count, remain_b) < std::tie(o.jelly_count, o.remain_b);
}
};
int find_maximum_unique(int x_total, int y_total, std::vector<int> an, std::vector<int> bn) {
std::vector<Data> dp(x_total+1, Data(0, 0)); // dp[i] = how many jelly count can do when `remain x` == i
dp[x_total] = Data(0, y_total);
std::vector<int> ord(an.size());
std::iota(ord.begin(), ord.end(), 0); // 0 1 2 3 4 5 6 7
std::sort(ord.begin(), ord.end(), [&](int u, int v){ return bn[u] < bn[v]; }); // sort by `b`
for (int i : ord) {
int curr_a = an[i]; // a = ? ? ? ? ?
int curr_b = bn[i]; // b = 1 2 3 4 5
for(int remain_a = 0; remain_a <= x_total; ++remain_a) {
dp[remain_a] = std::max({
// case 1: not neither buy from `a` or `b`
dp[remain_a],
// case 2: buy from `b` greedy
curr_b <= dp[remain_a].remain_b
? dp[remain_a].buy_b(curr_b) // greedy by `b` if possible
: dp[remain_a],
// case 3: buy from `a` dynamic programing
curr_a + remain_a <= x_total
? dp[remain_a + curr_a].increase_jelly_count() // dynamic programming on `a`
: dp[remain_a]
});
}
}
return std::max_element(dp.begin(), dp.end())->jelly_count; // dp[0].jelly_count
}
inline int input() {
int i; std::cin >> i; return i;
}
#ifdef KRIST_LOCAL
int main() {
assert(4 == find_maximum_unique(6, 12, Vec({5, 1, 5, 6, 3}), Vec({3, 5, 4, 6, 7})));
puts("pass");
// using namespace std;
// cin.sync_with_stdio(0);
// int n = input();
// int x = input();
// int y = input();
// std::vector<int> xn(n);
// std::vector<int> yn(n);
// rep(i, 0, n) xn[i] = input();
// rep(i, 0, n) yn[i] = input();
// cout << find_maximum_unique(x, y, xn, yn);
}
#endif
