Waiter's Problem

Interview

Time limit1sMemory limit512 MB

Summary

Given tip amounts that decay by one per minute of waiting, choose a serving order to maximize the total tips collected.

Level: Medium5 of 10
Topics: Greedy, Sorting, Math, Implementation
Solved: No attempts yet

Problem

Cafe Satori hires only experienced waiters, and there is a reason for that. Every day at noon, a crowd of hungry customers enters the cafe and waits to be served. The only waiter on duty has his hands full. Fortunately, his heroic work is rewarded with generous tips.

Each customer is willing to leave a specific amount of tip, provided he is served immediately. For each minute of waiting the tip decreases by one, until it reaches zero.

It takes one minute for the waiter to serve a customer. Solve the waiter's problem and calculate how much money he can get, provided he serves customers in an optimal order.

Input

The first line of input contains the number of test cases $z$ ( $1 \leq z \leq 10^9$ ). The descriptions of the test cases follow.

The first line of each test case contains the number of customers $n$ ( $1 \le n \le 100\,000$ ). The second line contains $n$ non-negative integers not exceeding $10^9$ : these are the amounts of tips the customers are willing to give initially.

The total number of customers in all test cases does not exceed $1\,000\,000$ .

Output

For each test case, output the maximum total amount of tips the waiter can get.

Examples1

Example 1
Input
```
1
6
0 9 9 1 7 5
```
Expected output
```
24
```