CF2089B2 Canteen (Hard Version)

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: 1. For each $ 0 \le i < n $ : $ t := \min(a_i, b_i), a_i := a_i - t, b_i := b_i - t $ ; 2. For each $ 0 \le i < n $ : $ c_i := a_{(i - 1) \bmod n} $ ; 3. 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 $ , and that $ k $ does not exceed the sum of $ a $ .

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

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