Cleaning the Phone

题意翻译

题目大意： 有 $n$ 个物品和一个最低价值 $m$ ，每一个物品有一个价值 $a_i$ 和 体积 $b_i$ 体积只有可能为 $1$ 或 $2$ 。 你需要选出几个物品，使得它们的价值和大于等于 $m$ 且使体积最小。 $T$组询问。 数据范围： $1 \leq t \leq 10^4$， $1 \leq n \leq 2 \cdot 10^5$ ，$1 \leq a_i \leq 10^9$， $1 \leq b_i \leq 2$。 保证 $\sum n \leq 2 \cdot 10^5$。

题目描述

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.

输入输出样例

输入样例 #1

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

输出样例 #1

2
-1
6
4
3

说明

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 $ .