El Pequeño Pez Cian está jugando a Slay the Spire II y ha elegido al personaje «La Silenciosa» (Silent).
El Pequeño Pez Cian ahora necesita combatir contra un «Amigo de Batalla» (Battle Friend). Inicialmente, tanto las acumulaciones de «Veneno» (Poison) del Amigo de Batalla como tu nivel de «Acelerante» (Accelerant) son $0$. En cada uno de los siguientes $n$ turnos, ocurrirán los siguientes eventos en orden:
Usar «Veneno Mortal» (Deadly Poison): aumenta las acumulaciones de Veneno del Amigo de Batalla en $x_i$.
Elegir si usar «Acelerante»: elige si aumentar tu nivel de Acelerante en $1$.
Activar el efecto de Veneno: sea $t$ tu nivel de Acelerante, repite el siguiente evento $t$ veces:
- Sea $x$ el número de acumulaciones de Veneno del Amigo de Batalla. Si $x > 0$, inflige $x$ puntos de daño al Amigo de Batalla y reduce las acumulaciones de Veneno en $1$; de lo contrario, si $x = 0$, no ocurre nada.
Ten en cuenta que tanto las acumulaciones de Veneno como el nivel de Acelerante se conservan entre turnos y no desaparecen.
El Pequeño Pez Cian quiere maximizar el daño total infligido al Amigo de Batalla durante estos $n$ turnos. Por favor, imprime dicho daño máximo.
Entrada
La entrada contiene múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T$), que indica el número de casos de prueba.
Para cada caso de prueba, la primera línea contiene un entero $n$ ($1 \le n \le 5000$).
La segunda línea contiene $n$ enteros $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$), que representan las acumulaciones de Veneno añadidas al Amigo de Batalla en cada turno.
Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^6$, y que la suma de $n^2$ en todos los casos de prueba no supera $10^8$.
Salida
Para cada caso de prueba, imprime una sola línea con un entero que represente el daño total máximo que se puede infligir al Amigo de Batalla en todos los turnos.
Ejemplo
Entrada de ejemplo 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
Salida de ejemplo 1
33 11 750 725