import java.util.*;
class jelly {
int find_maximum_unique(int x, int y, int[] a, int[] b) {
int N = a.length;
int[][] vals = new int[N][2];
for (int i = 0; i < N; i++)
vals[i] = new int[] {a[i],b[i]};
sort(vals);
long[][] dpX = new long[N+1][x+1];
for (int i = 0; i < N; i++) {
for (int j = 0; j <= x; j++) {
//buy in shop2
dpX[i+1][j] = dpX[i][j]+vals[i][1];
//buy in shop1
if (j >= vals[i][0])
dpX[i+1][j] = Math.min(dpX[i+1][j],dpX[i][j-vals[i][0]]);
}
}
int[][] dpY = new int[N+1][y+1];
for (int i = N-1; i >= 0; i--) {
for (int j = 0; j <= y; j++) {
//dont take this jelly
dpY[i][j] = dpY[i+1][j];
//take this jelly
if (j >= vals[i][1])
dpY[i][j] = Math.max(dpY[i][j], dpY[i+1][j-vals[i][1]]+1);
}
}
int ans = 0;
for (int i = N; i >= 0; i--) {
long budget = y-dpX[i][x];
if (budget >= 0)
ans = Math.max(ans, i+dpY[i][(int)budget]);
}
return ans;
}
void sort(int[][] arr) {
//Sort an array (immune to quicksort TLE)
Random rgen = new Random();
for (int i = 0; i < arr.length; i++) {
int randomPosition = rgen.nextInt(arr.length);
int[] temp = arr[i];
arr[i] = arr[randomPosition];
arr[randomPosition] = temp;
}
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] arr1, int[] arr2) {
return arr1[0]-arr2[0];
//Ascending order.
}
});
}
}
