Ferma


Submit solution

Points: 6
Time limit: 0.65s
Memory limit: 20M

Problem type

Furtunel și-a dat seama ca viața de programator nu îl satisface, așa că și-a cumparat o fermă și acum își încearcă norocul ca fermier. Pamântul lui de n km lățime și n km lungime este împărțit în n * n parcele de 1km x 1km. Ne vom referi în continuare la parcela de pe linia x si coloana y ca (x, y).

A sosit primăvara, așa că Furtunel trebuie să are pamântul, pentru a-l pregăti de semănat. Pentru asta el trebuie sa își cumpere un tractor. Furtunel nu este un prea bun șofer, astfel că dacă a pornit tractorul, nu îl poate opri decât dupa ce a parcurs exact n km. De asemenea, el refuză să meargă cu tractorul pe direcții neparalele cu marginile terenului. Dacă tractorul rămâne fără motorină înainte de terminarea celor n km, acesta se strică și întreaga carieră de fermier a lui Furtunel este compromisă.

Fiecare parcelă (x, y) are asociată o valoare M(x, y) care reprezintă câți litri de motorină sunt necesari pentru a parcurge celula respectivă. După ce o parcelă a fost arată o data, dacă tractorul ar fi să mai treacă odată pe acolo, acesta nu va mai consuma deloc motorină. Cantitatea de motorină consumată de tractor în parcurgerea unei linii sau unei coloane este egală cu suma valorilor M asociate parcelelor de pe linia sau coloana respectivă.

Cerință

Prețul unui tractor este direct proporțional cu capacitatea rezervorului său, iar Furtunel este destul de puternic impactat de interminabila criză economică, așa că nu vrea să cheltuie prea mulți bani. El vă roagă să îi spuneți care ar fi capacitatea minimă a rezervorului tractorului pe care să îl cumpere ca să poată ara tot pamântul.

Input

Se citește un număr natural N, si apoi se citesc N linii de câte N numere naturale separate printr-un spațiu.

Output

Se va afișa un număr care reprezenta capacitatea minimă cerută, exprimată în litri.

Restricții și precizări

  • 1 \le N \le 1000
  • Pentru cel puțin 30% din testele folosite la evaluare, 1 \le N \le 300
  • Suma celor N * N numere M(x, y) nu va depăși 2.000.000.000.
  • Furtunel poate pune motorină în tractor între două parcurgeri de linie/coloană.

Sample Input

3
6
1 4 3
2 2 5
0 1 3

Sample Output

6

Explicație

Furtunel începe prin a ara linia a 3-a, consumând 4l de motorină. Apoi umple rezervorul înapoi la 6l și continuă prin a ara prima coloană. După ce face din nou plinul, parcurge a 2-a coloană. Deși pentru parcurgerea acesteia ar consuma în mod normal 7l de benzină, parcela (3, 2) a mai fost deja arată odată, deci nu mai necesită consum de motorină. Deci tractorul are nevoie de 6l pentru a parcurge această coloană. Apoi parcurge linia 2, cu consum de 5l și linia 1 cu consum de 3l. Orice capacitate mai mică ar avea tractorul, Furtunel nu ar putea ara tot pamântul.

Întregul procedeu are loc dupa cum se vede în figură:


Comments

There are no comments at the moment.