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

Это easy версия задачи. Отличие между версиями заключается в том, что в этой версии $$$k=0$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

У Экраде есть две последовательности $$$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$$$, $$$k = 0$$$).

Вторая строка каждого набора входных данных содержит $$$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$$$.

Пример
Входные данные
4
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
Выходные данные
1
4
4
8
Примечание

В этой версии Экраде не может вносить изменения в $$$a$$$.

В первом наборе входных данных:

  • После первого раунда, $$$a=[0,0,0],b=[4,0,0]$$$.

Во втором наборе входных данных:

  • После первого раунда, $$$a=[3,0,0,1],b=[3,1,0,0]$$$;
  • После второго раунда, $$$a=[1,0,0,0],b=[0,1,0,0]$$$;
  • После третьего раунда, $$$a=[0,1,0,0],b=[0,1,0,0]$$$;
  • После четвертого раунда, $$$a=[0,0,0,0],b=[0,0,0,0]$$$.