D. Cleaning the Phone
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.
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\).
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.
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\).