A. Tuples
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ tuples $$$(a_i,b_i)(1 \leq a_i \leq 10^8,b_i=-1,1)$$$.

You can do the following operation:

  • Choose an integer $$$k(1\leq k \leq n)$$$;

  • Then choose $$$k$$$ different indexes $$$i_1,i_2,...,i_k$$$.

Your score is defined as $$$(a_{i_1}+a_{i_2}+...a_{i_k})(b_{i_1}+b_{i_2}+...b_{i_k})$$$.

Find the maximum score you can get.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of $$$3$$$ lines of input.

The first line contains an integer $$$n(1 \leq n \leq 2*10^5)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_{n}(1\leq a_i \leq 10^8)$$$.

The third line contains $$$n$$$ integers $$$b_1,b_2,...,b_{n}(b_i=-1,1)$$$.

The sum of $$$n$$$ will not exceed $$$2*10^5$$$.

Example
Input
3
5
1 1 1 3 3
1 1 1 -1 -1
3
1 2 3
1 1 1
3
2 1 3
-1 -1 -1
Output
12
18
-1
Note

Test case $$$1$$$:

Choose $$$k=4$$$ and $$$i_1=1,i_2=2,i_3=3,i_4=4$$$.

Test case $$$2$$$:

Choose $$$k=3$$$ and $$$i_1=1,i_2=2,i_3=3$$$.

Test case $$$3$$$:

Choose $$$k=1$$$ and $$$i_1=2$$$.