Concurso de Televisión


Con la finalidad de atraer a mayor audiencia el canal de TV de su localidad ha decido crear un concurso en el que va ha regalar dinero a los participantes.

El concurso consiste de una caja rectangular de bolas, donde cada bola tiene un numero entero que esta en el rango (−100 ≤ n ≤ 100). El concursante debe escoger un rango de bolas de la base y obtiene un premio en dinero equivalente a la suma de todas las bolas del rango que escogió y de todas las que están por encima de estas bolas.

Si escoge de las 6 columnas las que corresponden al rango rango de 1 a 5 se lleva el dinero que corresponde a las columnas 1,2,3,4 haciendo un total de 16 pesos.

Para no perder dinero en el concurso te piden hallar el máximo de dinero que un concursante puede obtener.

Entrada

La primera línea indica el número de casos de prueba. Cada caso de prueba consiste en varias líneas; la primera linea de cada caso de prueba tiene dos números que son las dimensiones de la matriz n,m, (1 ≤ n, m ≤ 100000). Luego siguen n filas cada una con m números separados por espacio.

Salida

Para cada caso de prueba, escriba una línea conteniendo el máximo número de pesos que un concursante puede ganar.

Ejemplo de Entrada

1
3 6
5 -1 -10 4 -1 3
1 -1 17 -2 3 1
7 -1 -8 4 -1 -8

Ejemplo de Salida

16

Código

CONCURSOTV

Intentos de resolución

205
48

Logrados

Etiquetas

#2016 #obi-departamental