After realizing that the previous problem was too difficult for the position as the third problem of the second round of VNOI CUP, the problem setters quickly came up with the following problem.

• Given two arrays of integers ~a~ and ~c~, both of length ~n~, find the minimum value of the following expression, where ~x~ is an arbitrary integer:

  $$\sum_{i=1}^n c_i \cdot |a_i - x|$$

However, the problem setters still don't know how to solve this problem. Can you help them?

Input

Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10\,000~). The description of each test case is as follows.

The first line contains an integer ~n~ (~1 \le n \le 3 \cdot 10^5~) — the length of arrays ~a~ and ~c~.

The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~-10^6 \le a_i \le 10^6~) — the elements of array ~a~.

The third line contains ~n~ integers ~c_1, c_2, \ldots, c_n~ (~-10^6 \le c_i \le 10^6~) — the elements of array ~c~.

The sum of ~n~ across all test cases is guaranteed not to exceed ~3 \cdot 10^5~.

Output

For each test case, if the value of the expression can go down to negative infinity, output ~\texttt{-inf}~. Otherwise, output the integer which is the minimum value of the expression.

Scoring

Sample Input 1

4
6
1 2 3 4 5 6
1 1 1 1 1 1
6
-4 -2 0 2 4 6
-1 -1 -1 -1 -1 -1
3
-100 0 100
1 0 -1
10
2 -8 4 -8 7 8 -1 -5 -7 -6
2 0 10 10 9 -4 -10 9 2 7

Sample Output 1

9
-inf
-200
158

Notes

In the first test case, with ~x = 3~, the value of the expression is ~9~. We can prove that there is no value of ~x~ that can make the expression smaller than ~9~.

In the second test case, as ~x~ approaches ~\infty~, the value of the expression approaches ~-\infty~.