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 < n)) such that (a_i > 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: For each (0 \le i < n): (t := \min(a_i, b_i), a_i := a_i - t, b_i := b_i - t); For each (0 \le i < n): (c_i := a_{(i - 1) \bmod n}); For each (0 \le i < 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! 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