← 返回题目列表

Codeforces · 2089/B2

B2. 食堂(硬版)

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

这是问题的困难版本。版本之间的区别在于,在此版本中,对 $$$k$$$ 没有额外的限制。只有解决了该问题的所有版本,您才能破解。

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

最初,Ecrade 可以对序列 $$$a$$$ 进行精确的 $$$k$$$ 更改。保证$$$k$$$不超过$$$a$$$的总和。在每次更改中:

  • 选择一个整数 $$$i$$$ ($$$0 \le i \lt n$$$) 使得 $$$a_i \gt 0$$$,并执行 $$$a_i := a_i - 1$$$。

那么Ecrade会对$$$a$$$和$$$b$$$依次执行以下三个操作,构成一轮操作:

  1. 对于每个 $$$0 \le i \lt n$$$: $$$t := \min(a_i, b_i), a_i := a_i - t, b_i := b_i - t$$$;
  2. 对于每个 $$$0 \le i \lt n$$$: $$$c_i := a_{(i - 1) \bmod n}$$$;
  3. 对于每个 $$$0 \le i \lt n$$$: $$$a_i := c_i$$$;

Ecrade 想知道 $$$a$$$ 中的所有元素在 $$$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, \ldots, a_{n - 1}$$$ ($$$1 \le a_i \le 10^9$$$)。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_0, b_1, \ldots, b_{n - 1}$$$ ($$$1 \le b_i \le 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。还保证在每个测试用例中$$$a$$$的总和不超过$$$b$$$的总和,并且$$$k$$$不超过$$$a$$$的总和。

输出

对于每个测试用例,输出 $$$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

注意

在第五个测试用例中,$$$a$$$ 中的所有元素在 $$$6$$$ 发生变化后变为 $$$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]$$$。