Hinded

문제

Juku on koolis teinud hulga kontrolltöid, mida hinnati $0\dots 1000\; \backslash ldots\; 100$ punktiga.

Juku vanaisa annab talle hinnete eest taskuraha. Vanaisa loeb tulemused üle $5050$ punkti headeks hinneteks ja tulemused alla $5050$ punkti halbadeks hinneteks. Täpsemalt liidab ta hinnete $5050$ punkti ületavad osad Juku taskurahale ning lahutab $5050$ punkti alla jäävad osad sealt maha. Näiteks hinnete $3535$, $4242$, $8181$ ja $100100$ eest saaks Juku kokku $(35-50)+(42-50)+(81-50)+(100-50)=-15-8+31+50=58(35-50)+(42-50)+(81-50)+(100-50)\; =\; -15-8+31+50\; =\; 58$ eurot. (Täpselt $5050$ punktiga hinnatud tööd seega taskuraha ei mõjuta.)

Õpetaja hoiab Juku hindeid $NN$ rea ja $NN$ veeruga Exceli tabelis. Kokku on Jukul seega $N^{2}N^2$ hinnet. Juku pääseb tabelile korraks ligi ja tal on võimalus oma hindeid "parandada" sel viisil, et ta märgib tabelis ühe ristkülikukujulise alamosa (mis võib olla ka tühi, s.t. sisaldada null elementi) ja kustutab sealt kõik hinded.

Leida, mis on maksimaalne hulk taskuraha, mille Juku võiks sellise kustutamise järel saada.

입력

Sisendi esimesel real on täisarv $NN$ ($2\le N\le 3002\; \backslash le\; N\; \backslash le\; 300$): õpetaja tabeli küljepikkus.

Järgmisel $NN$ real on igaühel $NN$ tühikutega eraldatud täisarvu lõigust $0\dots 1000\; \backslash ldots\; 100$: Juku hinded.

출력

Väljundisse kirjutada üks täisarv: Juku maksimaalse taskuraha summa.

3
80 90 90
100 5 60
90 60 10

200

4
100 100 100 100
100 2 2 100
100 90 90 100
100 2 2 100

500