B2. Canteen (Hard Version)
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The difference between the versions is that in this version, there are no additional limits on $$$k$$$. You can hack only if you solved all versions of this problem.

Ecrade has two sequences $$$a_0, a_1, \ldots, a_{n - 1}$$$ and $$$b_0, b_1, \ldots, b_{n - 1}$$$ consisting of integers. It is guaranteed that the sum of all elements in $$$a$$$ does not exceed the sum of all elements in $$$b$$$.

Initially, Ecrade can make exactly $$$k$$$ changes to the sequence $$$a$$$. It is guaranteed that $$$k$$$ does not exceed the sum of $$$a$$$. In each change:

  • Choose an integer $$$i$$$ ($$$0 \le i \lt n$$$) such that $$$a_i \gt 0$$$, and perform $$$a_i := a_i - 1$$$.

Then Ecrade will perform the following three operations sequentially on $$$a$$$ and $$$b$$$, which constitutes one round of operations:

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

Ecrade wants to know the minimum number of rounds required for all elements in $$$a$$$ to become equal to $$$0$$$ after exactly $$$k$$$ changes to $$$a$$$.

However, this seems a bit complicated, so please help him!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$0\le k\le 2\cdot 10^{14}$$$).

The second line of each test case contains $$$n$$$ integers $$$a_0, a_1, \ldots, a_{n - 1}$$$ ($$$1 \le a_i \le 10^9$$$).

The third line of each test case contains $$$n$$$ integers $$$b_0, b_1, \ldots, b_{n - 1}$$$ ($$$1 \le b_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$. It is also guaranteed that in each test case the sum of $$$a$$$ does not exceed the sum of $$$b$$$, and that $$$k$$$ does not exceed the sum of $$$a$$$.

Output

For each test case, output the minimum number of rounds required for all elements in $$$a$$$ to become equal to $$$0$$$ after exactly $$$k$$$ changes to $$$a$$$.

Example
Input
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
Output
1
4
4
8
0
2
2
1
Note

In the fifth test case, all elements in $$$a$$$ become $$$0$$$ after exactly $$$6$$$ changes.

In the sixth test case, Ecrade can do exactly one change to $$$a_3$$$, then $$$a$$$ will become $$$[1,2,2,4]$$$.

  • After the first round, $$$a=[3,0,0,0],b=[3,1,0,0]$$$;
  • After the second round, $$$a=[0,0,0,0],b=[0,1,0,0]$$$.

In the seventh test case, Ecrade can do exactly one change to $$$a_4$$$, then $$$a$$$ will become $$$[2,1,1,1]$$$.

  • After the first round, $$$a=[0,1,0,0],b=[0,1,1,0]$$$;
  • After the second round, $$$a=[0,0,0,0],b=[0,0,1,0]$$$.