B2. Столовая (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это hard версия задачи. Отличие между версиями заключается в том, что в этой версии нет дополнительных ограничений на $$$k$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

У Экраде есть последовательности $$$a_0, a_1, \ldots, a_{n - 1}$$$ и $$$b_0, b_1, \ldots, b_{n - 1}$$$, состоящие из целых чисел. Гарантируется, что сумма всех элементов $$$a$$$ не превышает сумму всех элементов $$$b$$$.

Сначала Экраде может сделать ровно $$$k$$$ изменений в последовательности $$$a$$$. Гарантируется, что $$$k$$$ не превосходит сумму $$$a$$$. В каждом изменении:

  • Выберите целое число $$$i$$$ ($$$0 \le i \lt n$$$), которое удовлетворяет условию $$$a_i \gt 0$$$, и выполните $$$a_i := a_i - 1$$$.

Затем Экраде выполнит следующие три операции последовательно над $$$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$$$;

Экраде хочет знать минимальное количество раундов, необходимых для того, чтобы все элементы в $$$a$$$ стали равны $$$0$$$ после ровно $$$k$$$ изменений в $$$a$$$.

Однако это кажется немного сложным, поэтому, пожалуйста, помогите ему!

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$ стали равны $$$0$$$ после ровно $$$k$$$ изменений в $$$a$$$.

Пример
Входные данные
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$$$ становятся $$$0$$$ после ровно $$$6$$$ изменений.

В шестом наборе входных данных Экраде может сделать ровно одно изменение к $$$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]$$$.

В седьмом наборе входных данных Экраде может сделать ровно одно изменение к $$$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]$$$.