CF1475D Cleaning the Phone

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

对于每个测试用例，输出一行： - 如果不存在可以释放至少 $m$ 单位内存的应用集合，输出 $-1$； - 如果存在，输出 Polycarp 失去的最小便利分。

在第一个测试用例中，最优方案是卸载编号为 $2$ 和 $5$ 的应用程序，释放 $7$ 单位内存，$b_2+b_5=2$。 在第二个测试用例中，卸载唯一的应用程序只能释放 $2$ 单位内存，不足所需的 $3$ 单位。 在第三个测试用例中，最优方案是卸载编号为 $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$。 由 ChatGPT 4.1 翻译