Polycarp trusts that assuming he eliminates applications with numbers i1,i2,… ,ik, he will free ai1+ai2+… +aik units of memory and lose bi1+bi2+… +bik accommodation focuses. For instance, on the off chance that n=5, m=7, a=[5,3,2,1,4], b=[2,1,1,2,1], Polycarp can uninstall the accompanying application sets (not all choices are recorded beneath
Correct answer will be upvoted else downvoted. Computer science.
Polycarp trusts that assuming he eliminates applications with numbers i1,i2,… ,ik, he will free ai1+ai2+… +aik units of memory and lose bi1+bi2+… +bik accommodation focuses.
For instance, on the off chance that n=5, m=7, a=[5,3,2,1,4], b=[2,1,1,2,1], Polycarp can uninstall the accompanying application sets (not all choices are recorded beneath):
applications with numbers 1,4 and 5. For this situation, it will free a1+a4+a5=10 units of memory and lose b1+b4+b5=5 accommodation focuses;
applications with numbers 1 and 3. For this situation, it will free a1+a3=7 units of memory and lose b1+b3=3 accommodation focuses.
applications with numbers 2 and 5. For this situation, it will free a2+a5=7 memory units and lose b2+b5=2 accommodation focuses.
Help Polycarp, pick a bunch of uses, with the end goal that if eliminating them will free basically m units of memory and lose the base number of accommodation focuses, or demonstrate that such a set doesn't exist.
Input
The principal line contains one integer t (1≤t≤104) — the number of experiments. Then, at that point, t experiments follow.
The principal line of each experiment contains two integers n and m (1≤n≤2⋅105, 1≤m≤109) — the number of utilizations on Polycarp's telephone and the number of memory units to be liberated.
The second line of each experiment contains n integers a1,a2,… ,an (1≤
The third line of each experiment contains n integers b1,b2,… ,bn (1≤bi≤2) — the comfort points of every application.
It is ensured that the amount of n over all experiments doesn't surpass 2⋅105.
Output
For each experiment, output on a different line:
- 1, in case there is no arrangement of uses, eliminating which will free essentially m units of memory;
the base number of accommodation focuses that Polycarp will lose if such a set exists.
Step by step
Solved in 4 steps with 1 images
