CF1995B2.Bouquet (Hard Version)

这是该问题的困难版本。唯一的区别在于，本版本中不再列出每朵花的花瓣数，而是为所有种类的花设置了花瓣数和该种花的数量。

有一个女孩正在为她的生日做准备，想要购买最美丽的花束。商店里共有 $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, \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, 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$ 片花瓣。

由 ChatGPT 4.1 翻译