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

Вам подарили новую игру под названием «Elatyh». В игре вам даются $$$n$$$ мечей, каждый из которых имеет свою силу. В частности, меч под номером $$$i$$$ имеет силу $$$a_i$$$. Игра состоит из $$$n$$$ уровней, на каждом из которых вы встретите монстра.

Вы начинаете на уровне $$$1$$$ и продвигаетесь дальше. Чтобы пройти уровень $$$i$$$ и перейти на уровень $$$i + 1$$$, требуется убить монстра на уровне $$$i$$$. Для убийства монстра на $$$i$$$-м уровне вам нужно нанести ему $$$b_i$$$ ударов мечом. Мечи в игре очень хрупкие, поэтому могут нанести лишь один удар, прежде чем сломаются. Если вы завершили $$$n$$$-й уровень или у вас недостаточно мечей, вы можете завершить игру и перейти к подсчету очков.

Перед игрой вам разрешается выбрать сложность игры. Если вы выбираете сложность $$$x$$$, то на монстров перестают действовать мечи, сила которых меньше чем $$$x$$$. Счет игры в этом случае равняется $$$x$$$ умноженное на количество пройденных уровней. Ваша задача — выбрать сложность игры так, чтобы максимизировать счет игры.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1\le a_i\le 10^9)$$$.

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ $$$(1\le b_i\le n)$$$.

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

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

Для каждого набора входных данных выведите одно целое число — максимальный счет игры.

Пример
Входные данные
5
3
1 3 4
2 1 1
2
2 3
1 1
4
1 2 3 4
2 2 1 1
6
4 4 1 4 5 4
2 2 4 1 2 2
10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1
Выходные данные
3
4
3
8
10000000000
Примечание

Рассмотрим первый набор входных данных. Оптимальная сложность для выбора равна $$$3$$$. Если сложность равна $$$3$$$, вы можете наносить удары мечами номер $$$2$$$ и $$$3$$$. С $$$2$$$ мечами вы можете пройти $$$1$$$ уровень, так что игровой счет равен $$$3\cdot 1 = 3$$$.