Der Kleine Cyanfisch spielt Slay the Spire II und hat den Charakter „Die Stille“ (Silent) gewählt.
Der Kleine Cyanfisch muss nun gegen einen „Kampffreund“ (Battle Friend) kämpfen. Zu Beginn betragen sowohl die „Gift“-Stapel (Poison) des Kampffreunds als auch deine „Beschleuniger“-Stufe (Accelerant) jeweils $0$. In jeder der nächsten $n$ Runden treten nacheinander die folgenden Ereignisse ein:
„Tödliches Gift“ (Deadly Poison) einsetzen: Erhöhe die Gift-Stapel des Kampffreunds um $x_i$.
Wählen, ob „Beschleuniger“ eingesetzt wird: Wähle, ob deine Beschleuniger-Stufe um $1$ erhöht werden soll.
Gifteffekt auslösen: Sei deine Beschleuniger-Stufe $t$; wiederhole das folgende Ereignis $t$-mal:
- Sei die Anzahl der Gift-Stapel des Kampffreunds $x$. Falls $x > 0$, füge dem Kampffreund $x$ Schadenspunkte zu und verringere die Gift-Stapel um $1$; andernfalls, falls $x = 0$, passiert nichts.
Beachte, dass sowohl die Gift-Stapel als auch die Beschleuniger-Stufe über Runden hinweg erhalten bleiben und nicht verschwinden.
Der Kleine Cyanfisch möchte den Gesamtschaden maximieren, der dem Kampffreund in diesen $n$ Runden zugefügt wird. Bitte gib diesen maximalen Schaden aus.
Eingabe
Die Eingabe enthält mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.
Für jeden Testfall enthält die erste Zeile eine ganze Zahl $n$ ($1 \le n \le 5000$).
Die zweite Zeile enthält $n$ ganze Zahlen $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$), die die in jeder Runde zum Kampffreund hinzugefügten Gift-Stapel angeben.
Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^6$ nicht überschreitet und die Summe von $n^2$ über alle Testfälle $10^8$ nicht überschreitet.
Ausgabe
Gib für jeden Testfall eine einzelne Zeile mit einer ganzen Zahl aus, die den maximalen Gesamtschaden angibt, der dem Kampffreund über alle Runden hinweg zugefügt werden kann.
Beispiel
Eingabe 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
Ausgabe 1
33 11 750 725