#713 New City Planning

Statement

Statement language

You are designing $N$ buildings. Building $i$ can have at most $A_i$ floors.

A building with $h$ floors increases the city's completion score by $B_h$ . The city's initial score is $0$ , and the height of each building must be a positive integer.

Find the maximum completion score.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the maximum completion score on one line.

Constraints

$1 \leq T \leq 10\,000$ .
$1 \leq N \leq 100\,000$ .
$1 \leq_{}$ ().

Subtasks

#	Score	Constraints
1	32	$N \leq 1000$ . $M \leq 1000$ . The sum of $N+M$ over all test cases is at most .

Samples

Input

Output

14
15

In the first test case, choose heights $1,1,3,3,5$ for the buildings, respectively. Their contributions are $2,2,3,3,4$ , so the completion score is , which is the maximum.