Sau khi nhận ra bài cũ quá khó với vị trí là bài thứ ba của vòng loại thứ hai của VNOI CUP, ban ra đề đã tức tốc nghĩ ra bài toán sau.

• Cho hai mảng số nguyên ~a~ và ~c~ cùng có độ dài ~n~, bạn hãy tìm giá trị nhỏ nhất của biểu thức sau, với ~x~ là một giá trị nguyên tùy chọn:

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

Tuy nhiên, ban ra đề vẫn không biết cách giải bài này. Các bạn hãy giúp ban ra đề nhé!

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \leq t \leq 10\,000~). Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 3 \cdot 10^5~) — độ dài của mảng ~a~ và ~c~.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~-10^6 \le a_i \le 10^6~) — các phần tử của mảng ~a~.

Dòng thứ ba chứa ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ (~-10^6 \le c_i \le 10^6~) — các phần tử của mảng ~c~.

Đảm bảo rằng tổng của ~n~ qua tất cả các test case không vượt quá ~3 \cdot 10^5~.

Output

Với mỗi test case, nếu giá trị của biểu thức có thể xuống tới âm vô cùng, in ra xâu ~\texttt{-inf}~. Nếu không, hãy in ra số nguyên là giá trị nhỏ nhất của biểu thức trên.

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

Ở test case đầu tiên, với ~x = 3~, giá trị của biểu thức là ~9~. Ta có thể chứng minh là không có giá trị ~x~ nào có thể làm biểu thức bé hơn ~9~.

Ở test case thứ hai, với ~x~ tiến tới ~\infty~, giá trị của biểu thức tiến tới ~-\infty~.