Zamierzasz kupić działkę w celu pozyskania surowców naturalnych i zależy ci na maksymalizacji zysku całej transakcji. Sprzedawca ma do sprzedania działkę składającą się z N2 kwadratowych działek jednostkowych (każda z działek jednostkowych jest kwadratem, a wszystkie te działki są identycznych rozmiarów) ułożonych w kwadrat o wymiarach N x N.
Na każdej z działek jednostkowych znajdują się surowce naturalne o różnej wartości, przy czym wartość ta dla każdej z działek jest liczbą całkowitą z przedziału [0, 99]. Sprzedawca jest zainteresowany sprzedażą dowolnego prostokątnego obszaru składającego się z całych działek jednostkowych, przy czym jako cenę sprzedaży ustalił wartość gruntu, g, jednej działki jednostkowej pomnożoną przez liczbę działek jednostkowych mieszczących się w sprzedawanym prostokątnym obszarze.
Zysk transakcji obliczany jest jako suma wartości surowców znajdujących się na zakupionych działkach pomniejszona o koszt gruntu.
Dane wejściowe zawierają klika zestawów danych. Pierwszy wiersz zestawu danych zawiera liczbę całkowitą określającą bok kwadratu N, przy czym 1 ≤ N ≤ 500. Drugi wiersz zawiera koszt zakupu jednej działki jednostkowej i jest on liczbą całkowitą taką, że 0 ≤ g ≤ 99. Każdy z kolejnych N wierszy zawiera N liczb całkowitych z przedziału [0, 99] rozdzielonych spacjami. Liczby te określają wartości surowców odpowiednich działek w kwadracie N x N.
Dane wejściowe zakończone są wierszem zawierającym jedno 0.
Dla każdego zestawu danych na wyjście należy wyprowadzić jedną liczbę całkowitą będącą maksymalnym możliwym zyskiem z całej transakcji.
7 50 73 79 50 50 8 7 21 29 39 60 11 99 81 50 36 95 10 11 68 12 84 44 88 95 29 23 42 36 33 39 1 59 47 61 25 88 54 46 71 3 18 30 91 37 32 91 97 94 93 4 20 5 8 12 19 7 4 11 9 8 3 4 16 8 11 14 17 0
185 0