beecrowd | 3148

The Garden

By Samuel Eduardo da Silva, IFSULDEMINAS/UFF BR Brazil

Timelimit: 1

The infamous Jardim de Muzambinho ... stage for performances by bands such as Queens of the Stone Age and Royal Blood, and a training venue for runners as it has a rectangular shape.

In 2020, the world was hit by the Coronga Virus, a virus that when infecting a person, causes infinite laughter that can even be lethal. Unfortunately, people had to stop attending the Garden thanks to the Coronga pandemic, which is very contagious and the Garden would be an easy target for people to be contaminated. This caused a lot of sadness in the city.

However, the city promised to be always dedicating the Garden so that when the pandemic is over, people can return to their activities in the Garden safely.

The city government then created a competition for the population: to create a robot that is able to fully dedicate O Jardim. Obviously it offered a good cash prize to the creator of the best robot.

You, who are not silly or anything, decided to use your talent in programming and win the competition.

Basically, O Jardim contains several bandstands that are the focus of Coronga (where people were most crowded). To help in the competition, the city has made available to each participant a sensor that can detect how many viruses exist in a given focus. The big problem is that Coronga is a very difficult virus to eliminate and your robot must be able to ingest some foci in order to be able to produce a good killer, based on the decoding of the ingested viruses.

You have mapped the bandstands by storing in an X vector the amount of virus that each bandstand initially contains. Outbreaks can be ingested or fused in any order.

You then created a system in which: initially your robot has 1 experience (exp), as it is the little that is known about Coronga. When a bandstand i is fused, Xi is eliminated for each exp point. This is because the initial mapping is only an indication of how many viruses are in that bandstand, possibly they have already multiplied.

For each outbreak, you have the option of ingesting the outbreak, increasing your exp by 1, or else purging the bandstand, killing exp * Xi virus, where Xi is the number of viruses in the i-th bandstand.

For example, if the garden has 3 bandstands, vector X could be: [3,2,5]. A possible solution would be the following:

First focus: ingest. Increases exp from 1 to 2;

Second focus: ingest. Increases exp from 2 to 3;

Third focus: pest control. Eliminates X [3] * exp = 5 * 3 = 15 viruses.

Soon the total number of viruses killed would be 15.

However, it is not the best solution, the optimum would be:

Second focus: ingest. Increases exp from 1 to 2.

First focus: pest control. Eliminates X [1] * exp = 3 * 2 = 6 viruses.

Third focus: pest control. Eliminates X [3] * exp = 5 * 2 = 10.

Therefore, the total number of viruses killed would be 16.

Well, finish your robot. Create an algorithm that, given the amounts of viruses in each bandstand in the mapping, is able to eliminate as many viruses as possible. Oh, and remember to fuse your robot later :)


The first line of the entry contains an integer t, indicating the number of test cases. The second line contains an integer n, indicating the number of bandstands. The third line contains n integers indicating the vector X.


1 <= t <= 10 ^ 5;

1 <= n <= 10 ^ 5;

<= Xi <= 10 ^ 7;


An integer indicating the maximum number of viruses that can be eliminated.

Input Samples Output Samples



3 2 2




3 2 5