Cleaning the Phone
Contest: Codeforces Round 697 (Div. 3)
Difficulty rating: 1800
Tags: binary search, dp, sortings, two pointers

Polycarp often uses his smartphone. He has already installed $$$n$$$ applications on it. Application with number $$$i$$$ takes up $$$a_i$$$ units of memory.

Polycarp wants to free at least $$$m$$$ units of memory (by removing some applications).

Of course, some applications are more important to Polycarp than others. He came up with the following scoring system — he assigned an integer $$$b_i$$$ to each application:

- $$$b_i = 1$$$ — regular application;
- $$$b_i = 2$$$ — important application.

According to this rating system, his phone has $$$b_1 + b_2 + \ldots + b_n$$$ convenience points.

Polycarp believes that if he removes applications with numbers $$$i_1, i_2, \ldots, i_k$$$, then he will free $$$a_{i_1} + a_{i_2} + \ldots + a_{i_k}$$$ units of memory and lose $$$b_{i_1} + b_{i_2} + \ldots + b_{i_k}$$$ convenience points.

For example, if $$$n=5$$$, $$$m=7$$$, $$$a=[5, 3, 2, 1, 4]$$$, $$$b=[2, 1, 1, 2, 1]$$$, then Polycarp can uninstall the following application sets (not all options are listed below):

- applications with numbers $$$1, 4$$$ and $$$5$$$. In this case, it will free $$$a_1+a_4+a_5=10$$$ units of memory and lose $$$b_1+b_4+b_5=5$$$ convenience points;
- applications with numbers $$$1$$$ and $$$3$$$. In this case, it will free $$$a_1+a_3=7$$$ units of memory and lose $$$b_1+b_3=3$$$ convenience points.
- applications with numbers $$$2$$$ and $$$5$$$. In this case, it will free $$$a_2+a_5=7$$$ memory units and lose $$$b_2+b_5=2$$$ convenience points.

Help Polycarp, choose a set of applications, such that if removing them will free at least $$$m$$$ units of memory and lose the minimum number of convenience points, or indicate that such a set does not exist.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — the number of applications on Polycarp's phone and the number of memory units to be freed.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the number of memory units used by applications.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 2$$$) — the convenience points of each application.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output on a separate line:

- -1, if there is no set of applications, removing which will free at least $$$m$$$ units of memory;
- the minimum number of convenience points that Polycarp will lose if such a set exists.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, it is optimal to remove applications with numbers $$$2$$$ and $$$5$$$, freeing $$$7$$$ units of memory. $$$b_2+b_5=2$$$.

In the second test case, by removing the only application, Polycarp will be able to clear only $$$2$$$ of memory units out of the $$$3$$$ needed.

In the third test case, it is optimal to remove applications with numbers $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$, freeing $$$10$$$ units of memory. $$$b_1+b_2+b_3+b_4=6$$$.

In the fourth test case, it is optimal to remove applications with numbers $$$1$$$, $$$3$$$ and $$$4$$$, freeing $$$12$$$ units of memory. $$$b_1+b_3+b_4=4$$$.

In the fifth test case, it is optimal to remove applications with numbers $$$1$$$ and $$$2$$$, freeing $$$5$$$ units of memory. $$$b_1+b_2=3$$$.

Example input:
5
5 7
5 3 2 1 4
2 1 1 2 1
1 3
2
1
5 10
2 3 2 3 2
1 2 1 2 1
4 10
5 1 3 4
1 2 1 2
4 5
3 2 1 2
2 1 2 1

Example output:
2
-1
6
4
3

Editorial:
Let's say we remove $$$x$$$ applications with $$$b_i=1$$$ and $$$y$$$ applications with $$$b_i=2$$$. Obviously, among all the applications with $$$b_i=1$$$, it was necessary to take $$$x$$$ maximum in memory (so we will clear the most memory).
Let's split all the applications into two arrays with $$$b_i=1$$$ and $$$b_i=2$$$ and sort them. Then you need to take a prefix from each array.
Let's iterate over which prefix we take from the first array. For it, we can uniquely find the second prefix (we remove applications until the sum exceeds $$$m$$$). If we now increase the first prefix by taking a new application, then we don't need to take any applications in the second array. This means that when the first prefix is increased, the second one can only decrease.
To solve the problem, you can use the two-pointer method.