#include <bits/stdc++.h> #include "jelly.h" using namespace std; const int MAXN = 6e5+2; const int inf = 1e9+69; int n,x,y,ans; vector<pair<int, int>> ab(2002); vector<vector<int>> sums(2001),dp(2001,vector<int>(10001,inf)); vector<int> b_suff[2001]; int how_many(int suffix, int remaining){ if(suffix>n) return 0; if(remaining<0) return 0; int xd = upper_bound(sums[suffix].begin(),sums[suffix].end(),remaining)-sums[suffix].begin(); return xd; } int find_maximum_unique(int x, int y, vector<int> a, vector<int> b){ int n = a.size(); for(int i=1; i<=n; i++){ab[i].first=a[i-1]; ab[i].second=b[i-1];} sort(ab.begin()+1,ab.begin()+1+n); for(int i=1; i<=n; i++){ for(int j=i; j<=n; j++) b_suff[i].push_back(ab[j].second); sort(b_suff[i].begin(),b_suff[i].end()); sums[i].resize(b_suff[i].size()); sums[i][0]=b_suff[i][0]; for(int j=1; j<b_suff[i].size(); j++) sums[i][j]=sums[i][j-1]+b_suff[i][j]; } dp[0][0]=0; for(int i=1; i<=n; i++){ for(int p=0; p<=x; p++){ if(dp[i-1][p]==inf) continue; if(p+ab[i].first<=x) dp[i][p+ab[i].first]=min(dp[i][p+ab[i].first],dp[i-1][p]); if(dp[i-1][p]+ab[i].second<=y) dp[i][p]=min(dp[i][p],dp[i-1][p]+ab[i].second); } for(int p=0; p<=x; p++){ if(dp[i][p]==inf) continue; if(dp[i][p]>y) continue; ans=max(ans,i+how_many(i+1,y-dp[i][p])); } } //cout << how_many(3,8) << "\n"; return ans; }