7. Chicago

Kvalitný Slovenský Provider je nový mobilný operátor, ktorý práve vyhral grant na pokrytie Chicaga. Žiaľ, dostali iba polovicu finančných prostriedkov o ktoré žiadali. Preto ich nový vysielač síce má neobmedzený dosah, ale funguje iba v štyroch smeroch – Sever, Východ, Juh a Západ.

Podľa podmienok grantu má Kvalitný Slovenský Provider vybudovať vysielače na strechách práve dvoch mrakodrapov. Vysielače chcú umiestniť tak, aby maximalizovali počet potenciálnych zákazníkov, teda tak, aby pokryli čo najväčšie množstvo obyvateľov Chicaga. Vašou úlohou je zistiť najväčší možný počet ľudí, ktorým vedia poskytnúť mobilné pripojenie.

Úloha

Chicago má tvar štvorcovej mriežky so stranou \(n\) políčok. Na každom políčku stojí mrakodrap, v ktorom býva daný počet ľudí. Každý vysielač pokryje všetkých obyvateľov tých mrakodrapov, ktoré sú od neho na Sever, Východ, Juh, alebo Západ. Budovu, na ktorej je postavený, vysielač nevie pokryť. Navyše, ani druhý vysielač ju nemôže pokryť, lebo ich signály sa tu vyrušia.

Vašou úlohou je pre dané rozloženie obyvateľov Chicaga nájsť najväčší možný počet potenciálnych zákazníkov pokrytých aspoň jedným z dvoch vysielačov.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(2\leq n\leq 300\)) udávajúce dĺžku strany Chicaga. Na každom z nasledujúcich \(n\) riadkov je \(n\) čísiel udávajúcich počty obyvateľov na jednotlivých políčkach štvorca. Počet obyvateľov na jednom políčku je nezáporný a neprevyšuje \(10^3\).

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo – maximálny možný počet potenciálnych zákazníkov.

Príklady

Input:

3
1 2 3
3 2 1
2 2 2

Output:

14

Vysielače môžu byť postavené napríklad na mrakodrapoch s jedným obyvateľom.

Input:

2
2 2
2 2

Output:

4

Každé rozmiestnenie vysielačov je optimálne. Dva mrakodrapy bez vysielača majú pokrytie, a dva mrakodrapy s vysielačom pokrytie nemajú.