Petit Poisson Cyan joue à Slay the Spire II et a choisi le personnage « La Silencieuse » (Silent).

Petit Poisson Cyan doit maintenant affronter un « Ami de Combat » (Battle Friend). Initialement, le nombre de charges de « Poison » de l'Ami de Combat ainsi que votre niveau d'« Accélérant » (Accelerant) valent tous deux $0$. Au cours des $n$ prochains tours, les événements suivants se produisent dans l'ordre à chaque tour :

1. Utiliser « Poison Mortel » (Deadly Poison) : augmente le nombre de charges de Poison de l'Ami de Combat de $x_i$.

2. Choisir d'utiliser ou non « Accélérant » : choisir d'augmenter ou non votre niveau d'Accélérant de $1$.

3. Déclencher l'effet de Poison : soit $t$ votre niveau d'Accélérant, répétez l'événement suivant $t$ fois :

   • Soit $x$ le nombre de charges de Poison de l'Ami de Combat. Si $x > 0$, infligez $x$ points de dégâts à l'Ami de Combat et diminuez le nombre de charges de Poison de $1$ ; sinon, si $x = 0$, rien ne se passe.

Notez que le nombre de charges de Poison et le niveau d'Accélérant sont conservés d'un tour à l'autre et ne disparaissent pas.

Petit Poisson Cyan souhaite maximiser le total des dégâts infligés à l'Ami de Combat au cours de ces $n$ tours. Veuillez afficher cette valeur maximale de dégâts.

Entrée

L'entrée contient plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier $n$ ($1 \le n \le 5000$).

La deuxième ligne contient $n$ entiers $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$), représentant le nombre de charges de Poison ajoutées à l'Ami de Combat à chaque tour.

Il est garanti que la somme des $n$ sur tous les cas de test ne dépasse pas $10^6$, et que la somme des $n^2$ sur tous les cas de test ne dépasse pas $10^8$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un entier représentant le total maximal de dégâts pouvant être infligés à l'Ami de Combat sur l'ensemble des tours.

Exemple

Entrée 1

4
5
1 1 0 3 7
3
0 3 2
9
9 9 8 2 4 4 3 5 3
13
1 1 4 5 1 4 1 9 1 9 8 1 0

Sortie 1

33
11
750
725