C. Погоня
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы и ваш друг Илья участвуете в личном соревновании по программированию, состоящем из множества этапов. За каждый этап участник может получить любое целое число баллов от $$$0$$$ до $$$100$$$ включительно, независимо от других участников.

Баллы, набранные участниками в отдельных этапах, используются для формирования суммарных результатов соревнования. Пусть к некоторому моменту времени прошло $$$k$$$ этапов. Тогда для каждого участника выбирается $$$k - \lfloor \frac{k}{4} \rfloor$$$ этапов, на которых он набрал наибольшее число баллов, и суммируются баллы на них. Полученное число и является суммарным результатом участника. (Здесь $$$\lfloor t \rfloor$$$ обозначает округление вниз до наибольшего целого числа, не большего $$$t$$$.)

Например, пусть прошло $$$9$$$ этапов, на которых вы набрали баллы $$$50, 30, 50, 50, 100, 10, 30, 100, 50$$$. Сначала выбираются $$$7$$$ этапов, на которых вы набрали наибольшее число баллов: например, это могут быть все этапы, кроме $$$2$$$-го и $$$6$$$-го. Тогда ваш суммарный результат равен $$$50 + 50 + 50 + 100 + 30 + 100 + 50 = 430$$$.

К данному моменту прошло $$$n$$$ этапов, и вам известны ваши баллы и баллы Ильи на каждом из этих этапов. Однако сколько ещё этапов будет в соревновании, неизвестно. Вам интересно, какое наименьшее число этапов ещё должно пройти, чтобы ваш результат хотя бы теоретически смог оказаться больше или равен результату Ильи. Найдите это число!

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — число прошедших этапов соревнования.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 100$$$) — ваши баллы на прошедших этапах.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 100$$$) — баллы Ильи на прошедших этапах.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — наименьшее число этапов, через которое ваш результат может оказаться больше или равен результату Ильи.

Если ваш результат уже и так не меньше результата Ильи, выведите $$$0$$$.

Пример
Входные данные
5
1
100
0
1
0
100
4
20 30 40 50
100 100 100 100
4
10 20 30 40
100 100 100 100
7
7 59 62 52 27 31 55
33 35 50 98 83 80 64
Выходные данные
0
1
3
4
2
Примечание

В первом наборе входных данных вы набрали $$$100$$$ баллов на единственном прошедшем этапе, а Илья — $$$0$$$. Значит, ваш суммарный результат ($$$100$$$) и так не хуже результата Ильи ($$$0$$$).

Во втором наборе входных данных вы набрали $$$0$$$ баллов на первом этапе, а Илья — $$$100$$$. Достаточно одного этапа с противоположным результатом, чтобы суммарный результат вас обоих стал равен $$$100$$$.

В третьем наборе входных данных ваш суммарный результат равен $$$30 + 40 + 50 = 120$$$, а Ильи — $$$100 + 100 + 100 = 300$$$. После трёх дополнительных этапов ваш результат может стать равен $$$420$$$, а Ильи — $$$400$$$.

В четвёртом наборе входных данных после четырёх дополнительных этапов ваш результат может стать равен $$$470$$$, а Ильи — $$$400$$$. Трёх этапов недостаточно.