VIII Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 29.05.2004

Opis

Tatuś małego Tomcia jest znanym na świecie arcymistrzem szachowym i bardzo chciałby, żeby jego synek podążył jego śladami. Dlatego zaczął go już uczyć grać w szachy, mimo młodego wieku chłopca. Niestety Tomciowi kiepsko idzie nauka, najwyraźniej nie ma do tego smykałki. Przez pierwsze trzy dni uczył się ruchów pionka, a przez następne 8 - ruchów skoczka (po jednym dniu na każdy ruch). Aktualnie uczy się ruchów wieży, z którą rodzi sobie dużo lepiej i szacuje się, że po drugim dniu opanuje w pełni jej możliwości. W każdym razie po pierwszym dniu Tomcio umie już poruszać się nią w poziomie. Chłopiec jeszcze nie wie jaka lekcja go czeka następnego dnia, więc jest święcie przekonany, że wieżę można przesunąć na dowolne pole w tym samym wierszu i na żadne inne.

Choć Tomcio nie radzi sobie za dobrze z szachami to ma smykałkę do matematyki. Wymyślił więc sobie własną zabawę, na podstawie nowo zdobytej wiedzy. Narysował sobie szachownicę (nie koniecznie o wymiarach 8x8, ale kwadratową) i powypisywał na jej polach różne liczby, po jednej na każdym polu. Następnie zaczął stawiać na polach wieże tak by suma liczb na polach zajętych przez nie była możliwie jak największa. Chłopiec może postawić dowolną liczbę wież (w razie czego pożyczy sobie z innego zestawu, których w domu ma pełno); gdy nie postawi ani jednej, przyjmuje się, że suma jest równa 0. Żeby zabawa nie była zbyt prosta, Tomcio trzyma się reguły, że żadne dwie wieże nie mogą stać na jednym polu, ani wzajemnie siebie atakować (według jego aktualnego stanu wiedzy o szachach).

Zadanie

Mając daną wielkość szachownicy oraz liczby jakie Tomcio powpisywał w pola szachownicy, podaj jaką największą sumę może uzyskać, stawiając wieże zgodnie z podanymi regułami.

Specyfikacja wejścia

W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (D ≤ 50), oznaczająca liczbę szachownic, które sobie Tomcio przygotował, a które są dalej opisane na wejściu. W pierwszym wierszu opisu szachownicy znajduje się jedna liczba całkowita N (1 ≤ N ≤ 200), mówiąca jaka jest wysokość i szerokość szachownicy. W kolejnych N wierszach opisu przedstawiona jest zawartość pól w kolejnych wierszach szachownicy. Tak więc w wierszu i-tym (spośród tych N) znajduje się N liczb całkowitych (z przedziału od –1.000.000 do 1.000.000), będących wartościami zapisanymi w kolejnych polach i-tego wiersza szachownicy.

Specyfikacja wyjścia

Dla każdej szachownicy jaką sobie Tomcio przygotował należy wypisać, w osobnym wierszu, jedną liczbę całkowitą - maksymalną sumę, jaką chłopiec może uzyskać.

Przykład

3
1
0
2
1 2
2 1
3
1 2 3
1 2 3
1 2 3

0
4
9