#include "jelly.h"
#include <vector>
#include <algorithm>
#include <map>
const int MAXMONEY = 10005;
class name{
public:
int x;
int y;
bool operator<(const name& other) const{
return x < other.x;
}
};
class node{
public:
int value;
int count;
node* left = nullptr;
node* right = nullptr;
};
int get_mid(int left,int right) {
return (right - left) / 2 + left;
}
int get_value(node* root) {
if(!root) return 0;
return root->value;
}
int get_count(node* root) {
if(!root) return 0;
return root->count;
}
void add(node* root,int pos,int value,int left = 0,int right = MAXMONEY) {
if(right == left) {
root->value = value;
root->count = 1;
return;
}
int mid = get_mid(left,right);
if(pos <= mid) {
if(root->left == nullptr) root->left = new node();
add(root->left,pos,value,left,mid);
}
else {
if(root->right == nullptr) root->right = new node();
add(root->right,pos,value,mid + 1,right);
}
root->value = get_value(root->left) + get_value(root->right);
root->count = get_count(root->left) + get_count(root->right);
}
int get_max_count(node* root,int max_value,int left = 0,int right = MAXMONEY) {
if(!root) return 0;
int mid = get_mid(left,right);
if(max_value >= get_value(root->left)) {
return get_count(root->left) + get_max_count(root->right,max_value - get_value(root->left),mid + 1,right);
}
else {
return get_max_count(root->left,max_value,left,mid);
}
}
int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
int N = a.size();
int ans = 0;
std::vector<name> v(N);
for(int q = 0;q < N;q++) {
v[q].x = a[q];
v[q].y = b[q];
}
std::sort(v.begin(),v.end());
std::vector<int> dp(MAXMONEY,20000);
dp[0] = 0;
std::vector<int> res(N,20000);
int min_require = 0;
for(int q = 0;q < N;q++) {
min_require += v[q].x;
for(int w = MAXMONEY - 1;w>=0;w--) {
if(w < v[q].x) break;
dp[w] = std::min(dp[w],dp[w - v[q].x] + v[q].y);
}
for(int w = std::max(0,min_require - x);w < MAXMONEY;w++) {
if(dp[w] <= y) {
res[q] = std::min(res[q],dp[w]);
}
}
}
if(res.back() <= y) return N;
std::vector<name> u(N);
for(int q = 0;q < N;q++) {
u[q].x = v[q].y;
u[q].y = q;
}
std::sort(u.begin(),u.end());
std::map<int,int> mm;
for(int q = 0;q < N;q++) {
mm[u[q].y] = q;
}
node* root = new node();
for(int q = N - 1;q>=1;q--) {
add(root,mm[q],u[q].x);
if(res[q - 1] <= y) {
int remain_value = y - res[q];
ans = std::max(ans,q + get_max_count(root,remain_value));
}
}
add(root,mm[0],u[0].x);
ans = std::max(ans,get_max_count(root,y));
return ans;
}
