← 返回题目列表

Codeforces · 1475/D

D. 清洁手机

中文机器翻译题面 查看原题

Polycarp 经常使用他的智能手机。他已经在上面安装了 $$$n$$$ 应用程序。编号为 $$$i$$$ 的应用程序占用 $$$a_i$$$ 内存单位。

Polycarp 希望释放至少 $$$m$$$ 单位的内存(通过删除一些应用程序)。

当然,某些应用对于 Polycarp 来说比其他应用更重要。他提出了以下评分系统 - 他为每个申请分配了一个整数 $$$b_i$$$:

- $$$b_i = 1$$$ — 常规申请;
- $$$b_i = 2$$$ — 重要应用。

根据这个评级系统,他的手机有 $$$b_1 + b_2 + \ldots + b_n$$$ 便利点。

Polycarp 认为,如果他删除编号为 $$$i_1、i_2、\ldots、i_k$$$ 的应用程序,那么他将释放 $$$a_{i_1} + a_{i_2} + \ldots + a_{i_k}$$$ 单位的内存并丢失 $$$b_{i_1} + b_{i_2} + \ldots + b_{i_k}$$$ 便利点。

例如,如果 $$$n=5$$$、$$$m=7$$$、$$$a=[5, 3, 2, 1, 4]$$$、$$$b=[2, 1, 1, 2, 1]$$$,则 Polycarp 可以卸载以下应用程序集(下面未列出所有选项):

- 编号为 $$$1、4$$$ 和 $$$5$$$ 的应用程序。在这种情况下,它将释放 $$$a_1+a_4+a_5=10$$$ 单位内存并失去 $$$b_1+b_4+b_5=5$$$ 便利点;
- 编号为 $$$1$$$ 和 $$$3$$$ 的应用程序。在这种情况下,它将释放 $$$a_1+a_3=7$$$ 单位内存并失去 $$$b_1+b_3=3$$$ 便利点。
- 编号为 $$$2$$$ 和 $$$5$$$ 的应用程序。在这种情况下,它将释放 $$$a_2+a_5=7$$$ 内存单元并失去 $$$b_2+b_5=2$$$ 便利点。

帮助 Polycarp,选择一组应用程序,这样如果删除它们将释放至少 $$$m$$$ 单位的内存并丢失最少数量的便利点,或者指示这样的一组不存在。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — Polycarp 手机上的应用程序数量和要释放的内存单元数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 应用程序使用的内存单元数。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 2$$$) - 每个应用程序的便利点。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在单独的行上输出:

- -1,如果没有应用程序集,则删除该应用程序将释放至少 $$$m$$$ 单位的内存;
- 如果存在这样的集合,Polycarp 将失去的最小便利点数量。

示例

输入 #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

注意

在第一个测试用例中,最好删除编号为 $$$2$$$ 和 $$$5$$$ 的应用程序,释放 $$$7$$$ 内存单位。 $$$b_2+b_5=2$$$。

在第二个测试用例中,通过删除唯一的应用程序,Polycarp 将能够仅清除所需的 $$$3$$$ 内存单元中的 $$$2$$$。

在第三个测试用例中,最好删除编号为 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$4$$$ 的应用程序,从而释放 $$$10$$$ 内存单位。 $$$b_1+b_2+b_3+b_4=6$$$。

在第四个测试用例中,最好删除编号为 $$$1$$$、$$$3$$$ 和 $$$4$$$ 的应用程序,从而释放 $$$12$$$ 内存单位。 $$$b_1+b_3+b_4=4$$$。

在第五个测试用例中,最好删除编号为 $$$1$$$ 和 $$$2$$$ 的应用程序,释放 $$$5$$$ 内存单位。 $$$b_1+b_2=3$$$。