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$.

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]$.