Kule
Ploča se sastoji od kvadratnih polja pravilno poredanih u N redaka i N stupaca, a na svakom polju se nalazi po jedan cijeli broj. Imamo dvije kule koje moramo postaviti na dva različita polja. Za neko polje na ploči kažemo da je napadnuto ako se nalazi u istom retku ili istom stupcu kao i neka od kula. Polja na kojima se nalaze kule ne smatramo napadnutima. Želimo postaviti kule tako da zbroj brojeva na svim napadnutim poljima bude što je veći mogući. Napišite program koji će odrediti koliki je taj maksimalni zbroj.
InputU prvom retku se nalazi prirodni broj N, 2 ≤ N ≤ 300. U svakom od sljedećih N redaka se nalazi po N cijelih brojeva. Svaki od njih će biti veći ili jednak od 0 i manji ili jednak od 1000, a oni redom predstavljaju brojeve koji se nalaze na ploči, odozgo prema dolje i slijeva na desno.
OutputU prvi i jedini redak treba ispisati traženi maksimalni zbroj.
Ulaz
3
0 1 4
3 0 2
1 4 1 Izlaz
15Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.