D. Друзья и ресторан
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Компания из $$$n$$$ друзей решила сходить в ресторан. Каждый из друзей планирует сделать заказ на $$$x_i$$$ бурлей, а всего у него есть $$$y_i$$$ бурлей ($$$1 \le i \le n$$$).

Компания решила разбить посещение ресторана на несколько дней. Каждый день в ресторан отправляется некоторая группа из хотя бы двух друзей. Каждый из друзей посещает ресторан не более одного раза (то есть эти группы не пересекаются). Эти группы должны удовлетворять условию: суммарный бюджет каждой группы должен быть не меньше суммы, которую собираются потратить друзья из группы в ресторане. Другими словами, сумма всех значений $$$x_i$$$ в группе не должна превышать сумму значений $$$y_i$$$ в группе.

Какое максимальное количество дней друзья могут посещать ресторан?

Например, пусть есть $$$n = 6$$$ друзей, для которых $$$x$$$ = [$$$8, 3, 9, 2, 4, 5$$$], а $$$y$$$ = [$$$5, 3, 1, 4, 5, 10$$$]. Тогда:

  • Первый и шестой друзья могут пойти в ресторан в первый день. Они потратят в ресторане $$$8+5=13$$$ бурлей, а их суммарный бюджет составляет $$$5+10=15$$$ бурлей. Так как $$$15 \ge 13$$$, то они в самом деле могут образовать группу.
  • Друзья с номерами $$$2, 4, 5$$$ могут образовать вторую группу. Они потратят в ресторане $$$3+2+4=9$$$ бурлей, а их общий бюджет составит $$$3+4+5=12$$$ бурлей ($$$12 \ge 9$$$).

Можно показать, что образовать большее число групп так, чтобы в каждой группе было хотя бы два друга и можно было оплатить счёт, они не смогут.

Таким образом, максимальное количество групп, на которое могут разбиться друзья равно $$$2$$$. Друзья будут посещать ресторан максимум два дня. Отметим, что $$$3$$$-й из друзей не посетит ресторан вообще.

Выведите максимальное количество дней посещения ресторана по заданным $$$n$$$, $$$x$$$ и $$$y$$$.

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

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

Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных записано единственное целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество друзей.

Во второй строке каждого набора входных данных записано ровно $$$n$$$ целых чисел $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^9$$$). Значение $$$x_i$$$ соответствует количеству бурлей, которое друг под номером $$$i$$$ планирует потратить в ресторане.

В третьей строке каждого набора входных данных записано ровно $$$n$$$ целых чисел $$$y_1, y_2, \dots, y_n$$$ ($$$1 \le y_i \le 10^9$$$). Значение $$$y_i$$$ соответствует количеству бурлей, которое есть у друга под номером $$$i$$$.

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

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

Для каждого набора входных данных выведите максимальное количество дней посещения ресторана. Если друзья не могут образовать даже одну группу для посещения, то выведите 0.

Пример
Входные данные
6
6
8 3 9 2 4 5
5 3 1 4 5 10
4
1 2 3 4
1 1 2 2
3
2 3 7
1 3 10
6
2 3 6 9 5 7
3 2 7 10 6 10
6
5 4 2 1 8 100
1 1 1 1 1 200
6
1 4 1 2 4 2
1 3 3 2 3 4
Выходные данные
2
0
1
3
1
3
Примечание

Первый набор входных данных разобран в условии.

Во втором наборе входных данных примера друзья не могут образовать хотя бы одну группу из двух или более человек.

В третьем наборе входных данных один из способов посещать ресторан в течение одного дня — отправиться группой из всех трёх друзей ($$$1+3+10 \ge 2+3+7$$$). Заметим, что возможности разбиться на две группы у них нет.