19358번 - Waiter's Problem 다국어

문제

Cafe Satori hires only experienced waiters, and there is a reason for that. Everyday during lunchtime, at 12:00 noon, a horde of hungry customers enters the cafe and waits to be served. Therefore, the only waiter on duty has his hands full. Fortunately, his heroic work will be 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.

입력

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円$.

출력

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

제한

힌트