Question
Spell Splice
Gaurav has N magic spells. The ith spell has a volatility of Vi and a strength of Ai. When spells i and j (1 ≤ i < j ≤ N) are activated together, they merge to form a single spell of strength (Ai × Vj + Vi × Aj).
What's the maximum possible strength of a spell Chef can obtain by activating exactly two of his spells?
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains a single integer N, the number of spells.
The next N lines describe the spells. The ith of them contains two space-separated integers Vi and Ai - the volatility and strength of the ith spell.
Constraints
1 ≤ T ≤ 102
2 ≤ N ≤ 100
1 ≤ Ai, Vi ≤ 1000
Each test case consists of multiple lines of input.
The first line of each test case contains a single integer N, the number of spells.
The next N lines describe the spells. The ith of them contains two space-separated integers Vi and Ai - the volatility and strength of the ith spell.
Constraints
1 ≤ T ≤ 102
2 ≤ N ≤ 100
1 ≤ Ai, Vi ≤ 1000
Output
For each test case, output on a new line the maximum possible power of a combined spell.
Example
Sample Input
1
2
1 10
5 5
Sample Output
55
Explanation
Test case 1 There are only two spells. Combining them results in a spell of strength of 1×5 + 5×10 = 55.
1
2
1 10
5 5
Sample Output
55
Explanation
Test case 1 There are only two spells. Combining them results in a spell of strength of 1×5 + 5×10 = 55.