B2. 花束（困难版）
每测试点时间限制：1.5 秒
内存限制：256 兆字节

本题为困难版本。唯一区别在于：在本版本中，每种花的花瓣数和数量均已给出，而非仅列出花瓣数。

一位女孩正在准备她的生日，想要购买最漂亮的花束。商店里共有 $n$ 种不同类型的花，每种花由其花瓣数和该种花的数量描述。一朵有 $k$ 片花瓣的花花费 $k$ 枚硬币。女孩决定，她用于装饰蛋糕的任意两朵花的花瓣数之差不能超过 $1$。同时，女孩希望组装的花束花瓣总数尽可能多。可惜她只有 $m$ 枚硬币，不能超支。请问她能够组装的花束的最大可能花瓣总数是多少？

输入

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10\,000$）——测试用例的数量。接下来是各个测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$（$1 \le n \le 2 \cdot 10^5$，$1 \le m \le 10^{18}$）——商店中花的种类数，以及女孩拥有的硬币数。
每个测试用例的第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），其中 $a_i$ 是第 $i$ 种花的花瓣数（对于不同下标 $i \ne j$，保证 $a_i \ne a_j$）。
每个测试用例的第三行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le 10^9$），其中 $c_i$ 是第 $i$ 种花在商店中的数量。

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

输出

对于每个测试用例，输出一个整数——在满足所有给定条件的前提下，女孩能够收集到的花束的最大可能花瓣总数。

示例

输入

7
3 10
1 2 3
2 2 1
3 1033
206 207 1000
3 4 1
6 20
4 2 7 5 6 1
1 2 1 3 1 7
8 100000
239 30 610 122 24 40 8 2
12 13123 112 1456 124 100 123 10982
6 13
2 4 11 1 3 5
2 2 1 2 2 1
8 10330
206 210 200 201 198 199 222 1000
9 10 11 12 13 14 15 16
2 10000000000
11 12
87312315 753297050

输出

7
1033
19
99990
13
10000
9999999999

说明

在第一个测试用例中，一些合法的花束为：$(1,1,2,2)$，$(2,2,3)$，$(1,1)$，$(2,2)$。在不超过 $10$ 枚硬币的所有合法花束中，最大值是 $7$，对应花束 $(2,2,3)$。
在第二个测试用例中，可以组装一个合法花束 $(206,206,207,207,207)$，花瓣总数为 $1033$，这是女孩能买到的最大花瓣数。
在第三个测试用例中，可以组装一个合法花束 $(5,5,5,4)$，花瓣总数为 $19$。可见没有合法花束能达到 $20$ 片花瓣。