← 返回题目列表

Codeforces · 1995/B2

B2. 花束(硬版)

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

这是问题的困难版本。唯一的区别是,在这个版本中,不是列出每朵花的花瓣数量,而是为所有类型的鲜花设置了花瓣数量和商店中的鲜花数量。

一个女孩正在准备她的生日,想要买一束最美丽的花束。店里一共有$$$n$$$种不同类型的鲜花,每种鲜花的特征是花瓣数量和该类型鲜花的数量。一朵有 $$$k$$$ 花瓣的花需要 $$$k$$$ 硬币。女孩决定,她用来装饰蛋糕的任何两朵花之间的花瓣数量差异不应超过一朵。与此同时,女孩想要组装一束花瓣数量尽可能多的花束。不幸的是,她只有 $$$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, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是商店中第 $$$i$$$ 花型的花瓣数量(对于不同的索引 $$$i \neq j$$$,它必须是$$$a_i \neq a_j$$$)。每个测试用例的第三行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$),其中 $$$c_i$$$ 是商店中第 $$$i$$$ 种花的数量。

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

输出

对于每个测试用例,打印一个整数 - 女孩在遵守上面列出的所有条件的情况下可以收集的花束中的最大可能花瓣数。

示例

输入 #1

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

输出 #1

7
1033
19
99990
13
10000
9999999999

注意

在第一个测试用例中,一些有效的花束是 $$$(1, 1, 2, 2), (2, 2, 3), (1, 1), (2, 2)$$$。 $$$(2, 2, 3)$$$ 的所有有效花束不超过 $$$10$$$ 的最大值为 $$$7$$$。在第二个测试用例中,您可以用 $$$(206, 206, 207, 207, 207)$$$ 组装一个有效的花束,总和为 $$$1033$$$,这是女孩可以购买的最大花瓣数。在第三个测试用例中,您可以用 $$$(5, 5, 5, 4)$$$ 组装一个有效的花束,总和为 $$$19$$$。可以看出,有效的花束不能有 $$$20$$$ 花瓣。