P1050清仓甩卖（sale）

【题目背景】

Celia 逛超市时，经常喜欢挑选性价比更高的商品，俗称为“物美价廉”。

【题目描述】

小 X 的促销计划十分成功，现在糖果店中只剩下了 $n$ 颗糖果，其中第 $i$ 颗糖果的原价为 $w_i$ 元。为了尽快清空余货，小 X 为每颗糖果标出了清仓价格。第 $i$ 颗糖果的清仓价格为 $v_i$ 元，其中**$v_i\in\{1,2\}$**。

小 R 带着 $m$ 元来到糖果店，可以任意选择若干颗糖果购买。所选糖果的清仓价格之和称为这次购买的总价格，原价之和称为这次购买的总价值。小 R 要求总价格不超过 $m$，并希望总价值尽可能大。

你需要帮助小 R 求出能够得到的最大总价值。

【输入格式】

本题包含多组测试数据。

从文件 $\textbf{\textit{sale.in}}$ 中读入数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据。对于每组测试数据：

第一行包含两个正整数 $n,m$，分别表示糖果数量与小 R 拥有的钱数。

第二行包含 $n$ 个正整数 $w_1,w_2,\ldots,w_n$，其中 $w_i$ 表示第 $i$ 颗糖果的原价。

第三行包含 $n$ 个正整数 $v_1,v_2,\ldots,v_n$，其中 $v_i$ 表示第 $i$ 颗糖果的清仓价格。

【输出格式】

输出到文件 $\textbf{\textit{sale.out}}$ 中。

对于每组测试数据，输出一行一个非负整数，表示小 R 能够得到的最大总价值。

【样例 1 输入】

10 125 538 7 10 5 641 2 2 1 2

【样例 1 输出】

125

【说明/提示】

【样例 1 解释】

小 R 可以购买第 $1,2,3$ 颗糖果。这次购买的总价格为 $1+2+2=5$，总价值为 $8+7+10=25$。

可以证明，不存在总价值更大的合法购买方案。

【样例 2】

见选手目录下的 $\textbf{\textit{sale/sale2.in}}$ 和 $\textbf{\textit{sale/sale2.ans}}$。

该附加样例满足测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{sale/sale3.in}}$ 和 $\textbf{\textit{sale/sale3.ans}}$。

该附加样例满足测试点 $9\sim 12$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{sale/sale4.in}}$ 和 $\textbf{\textit{sale/sale4.ans}}$。

该附加样例满足测试点 $13\sim 19$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{sale/sale5.in}}$ 和 $\textbf{\textit{sale/sale5.ans}}$。

该附加样例满足测试点 $20\sim 25$ 的数据范围。

【数据范围】

设 $N$ 为单个测试点内所有测试数据的 $n$ 之和。

对于所有测试数据，保证：

• $0\leq c\leq25$，$1\leq T\leq5\times10^4$。
• $1\leq n\leq2\times10^5$，$N\leq5\times10^5$。
• $1\leq m\leq2n$。
• 对于所有 $1\leq i\leq n$，均有 $1\leq w_i\leq10^9$，$v_i\in\{1,2\}$。