Lotus and Characters

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 262144/131072 K (Java/Others)

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.

Sample Input

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

Sample Output

35 5

Hint

jiangzijing2015

Source

BestCoder Round #91

提交代码