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.
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.
Para cada caso de prueba, escriba una línea conteniendo el máximo número de pesos que un concursante puede ganar.
1 3 6 5 -1 -10 4 -1 3 1 -1 17 -2 3 1 7 -1 -8 4 -1 -8
16
#2016 #obi-departamental