D. Monster Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have been gifted a new game called "Elatyh". In the game, you are given $$$n$$$ swords, each with its own strength. In particular, the sword numbered $$$i$$$ has a strength of $$$a_i$$$. The game consists of $$$n$$$ levels, each of which features a monster.

You start at level $$$1$$$ and progress further. To pass level $$$i$$$ and move on to level $$$i + 1$$$, you need to defeat the monster at level $$$i$$$. To defeat the monster at level $$$i$$$, you need to deal it $$$b_i$$$ sword strikes. The swords in the game are very fragile, so they can only deal one strike before breaking. If you complete level $$$n$$$ or run out of swords, you can finish the game and proceed to score calculation.

Before the game, you are allowed to choose the difficulty level. If you choose difficulty $$$x$$$, swords with a strength less than $$$x$$$ will not affect the monsters. The game score in this case is equal to $$$x$$$ multiplied by the number of levels completed. Your task is to choose the game difficulty in such a way as to maximize the game score.

Input

Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The following describes the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1\le a_i\le 10^9)$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ $$$(1\le b_i\le n)$$$.

It is guaranteed that the sum of the values of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the maximum game score.

Example
Input
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
Output
3
4
3
8
10000000000
Note

Consider the first test case. Optimal difficulty to choose is $$$3$$$. If difficulty is $$$3$$$, you can deal strikes with swords number $$$2$$$ and $$$3$$$. With $$$2$$$ swords you can complete $$$1$$$ level, so the game score is $$$3\cdot 1 = 3$$$.