Problem Description

Lotus has $n$ kinds of characters,each kind of characters has a value and a amount.She wants to construct a string using some of these characters.Define the value of a string is:its first character's value*1+its second character's value *2+...She wants to calculate the maximum value of string she can construct.
Since it's valid to construct an empty string,the answer is always $\geq 0$。

Input

First line is $T(0 \leq T \leq 1000)$ denoting the number of test cases.
For each test case,first line is an integer $n(1 \leq n \leq 26)$,followed by $n$ lines each containing 2 integers $val_i,cnt_i(|val_i|,cnt_i\leq 100)$,denoting the value and the amount of the ith character.

Output

For each test case.output one line containing a single integer,denoting the answer.

2
2
5 1
6 2
3
-5 3
2 1
1 1

35
5