AlgoLiga 2018

Dobra i zła energia

    Jasiu posiada sporo działek i na każdej z nich postanowił wybudować dom, który będzie miał jak najwięcej pozytywnej energii. Jasiu swoje działki podzielił na jednostkowe pola prostokątne i poprosił o pomoc różdżkarza, by ten sprawdził każdą działkę i każdemu polu jednostkowemu przypisał wartość dobrej bądź złej energii. Różdżkarz swoją niezawodną różdżką każdemu polu przyporządkował pewną wartość (dodatnią, ujemną lub zero) w zależności od rodzaju i siły energii w tym miejscu. Jasiu mając te dane w postaci kwadratowej macierzy postanowił, że wybuduje dom na takim terenie prostokątnym złożonym z jednostkowych pól, w którym suma wartości energii wszystkich pól tego terenu będzie możliwie największa. Pomóż Jasiowi wyznaczyć te sumy na wszystkich jego działkach, a on już sam zajmie się budową domów.

Wejście
W pierwszym wierszu znajduje się wejścia liczba d działek Jasia (2 ≤ d ≤ 100)
Dla każdej działki w osobnym wierszu podana jest jedna liczba n (2 ≤ n ≤ 100) - wymiar podzielonej na jednostkowe pola działki.
Dalej n wierszy, w każdym wierszu n liczb całkowitych a_ij (-100 ≤ a_ij ≤ 100), gdzie a_ij to wartość energii w danym polu jednostkowym.

Wyjście
Na wyjściu należy wypisać d wierszy, w każdym wierszu jedna liczba całkowita - największa możliwa suma wartości energii wyznaczona przez pewien prostokątny obszar działki.

Przykład

Wejście
2
3
11 -2 3
-7 0 -6
2 8 3
5
5 2 -18 6 5
-2 3 1 -8 2
7 -7 3 4 11
-6 2 4 1 -5
7 7 -9 -8 6

Wyjście
13
20

Wyjaśnienie
Szary kolor wyznacza prostokątny obszar o największej sumie wartości energii odpowiednio na pierwszej działce równej 13 i na drugiej równej 20.