B2. 食堂（困难版） 每个测试点时间限制：2 秒 每个测试点内存限制：512 兆字节

这是该问题的困难版本。两个版本的区别在于：在此版本中，对 $k$ 没有额外限制。只有当你解决了该问题的所有版本时，才能进行 Hack。

Ecrade 有两个由整数构成的序列 $a_0, a_1, \dots, a_{n-1}$ 和 $b_0, b_1, \dots, b_{n-1}$。保证 $a$ 中所有元素的和不超过 $b$ 中所有元素的和。

初始时，Ecrade 可以对序列 $a$ 进行 恰好 $k$ 次修改。保证 $k$ 不超过 $a$ 的和。每次修改如下：

· 选择一个下标 $i$（$0 \le i < n$），且满足 $a_i > 0$，然后执行 $a_i := a_i - 1$。

随后，Ecrade 会按顺序执行以下三个操作，这构成 一轮操作：

1. 对每个 $0 \le i < n$：令 $t := \min(a_i, b_i)$，然后 $a_i := a_i - t$，$b_i := b_i - t$；
2. 对每个 $0 \le i < n$：令 $c_i := a_{(i-1) \bmod n}$；
3. 对每个 $0 \le i < n$：令 $a_i := c_i$。

Ecrade 想知道：在恰好进行 $k$ 次修改后，使得 $a$ 中所有元素变为 $0$ 所需的最少轮数。

然而这似乎有些复杂，请帮他求解！

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来是每个测试用例的描述：

· 第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$0 \le k \le 2 \cdot 10^{14}$）； · 第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$（$1 \le a_i \le 10^9$）； · 第三行包含 $n$ 个整数 $b_0, b_1, \dots, b_{n-1}$（$1 \le b_i \le 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。同时保证在每个测试用例中，$a$ 的元素和不超过 $b$ 的元素和，并且 $k$ 不超过 $a$ 的元素和。

输出格式

对于每个测试用例，输出一行一个整数，表示在恰好进行 $k$ 次修改后，使 $a$ 中所有元素变为 $0$ 所需的最少轮数。

样例输入

8
3 0
1 1 4
5 1 4
4 0
1 2 3 4
4 3 2 1
4 0
2 1 1 2
1 2 2 1
8 0
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
3 6
1 1 4
5 1 4
4 1
1 2 3 4
4 3 2 1
4 1
2 1 1 2
1 2 2 1
4 2
2 1 1 2
1 2 2 1

样例输出

1
4
4
8
0
2
2
1

样例解释

· 在第五个测试用例中，经过恰好 $6$ 次修改后，$a$ 中所有元素变为 $0$。 · 在第六个测试用例中，Ecrade 可以对 $a_3$ 进行恰好一次修改，此时 $a$ 变为 $[1,2,2,4]$。 第一轮操作后：$a = [3,0,0,0],\ b = [3,1,0,0]$； 第二轮操作后：$a = [0,0,0,0],\ b = [0,1,0,0]$。 · 在第七个测试用例中，Ecrade 可以对 $a_4$ 进行恰好一次修改，此时 $a$ 变为 $[2,1,1,1]$。 第一轮操作后：$a = [0,1,0,0],\ b = [0,1,1,0]$； 第二轮操作后：$a = [0,0,0,0],\ b = [0,0,1,0]$。