描述
There are n chemical elements. Each of them has two attributes, a and b. When two different elements are mixed, a chemical reaction will occur. During a chemical reaction, energy will be released. The following expression tells the amount of energy that is released when i-th element and j-th element are mixed:
|ai - aj| ∙ bi ∙ bj / max(|bi|, |bj|)
Could you find the maximal energy that can be released by mixing two elements?
Note that the value of the expression may be negative, which means the chemical reaction absorbs energy. For simplicity, we regard it as releasing negative energy, so you can compare two values of the expression directly to determine which releases more energy.
输入
The first line contains an integer T (1 ≤ T ≤ 10) -- the number of test cases.
For each test case:
The first line contains an integer n. 2 ≤ n ≤ 500 000.
Then follows n lines, each line contains two integers: a, b, indicate the two attributes of a chemical element. 0 ≤ | a | ≤ 10 000. 1 < | b | ≤ 10 000.
输出
For each test case, output one integer in a single line -- the maximal energy that can be released by mixing two elements.
样例输入
1
5
1 5
-2 4
3 7
5 -3
-6 -2
样例输出
22
