Laiko ribojimas: 2s

Atminties ribojimas: 128MB

Duomenų failas: estafetes.in

Rezultatų failas: estafetes.out

Jei norite pateikti savo sprendimą - prisijunkite.

Estafetės

Jonas kartu su Tomu dalyvauja komandinėse estafetės varžybose. Varžybos vyks dideliame n aukščio bei pločio kvadrate. Kvadratas padalintas į n*n langelių ir kiekviename langelyje įrašytas skaičius a_(i,j).

Pradžioje Jonas stovi langelyje koordinatėmis (1,1), o Tomas langelyje koordinatėmis (n,n). Prasidėjus estafetei Jonas bėga link Tomo. Jonas iš langelio (i,j) gali judėti į langelį (i+1,j) arba į langelį (i,j+1). Jonui pasiekus Tomą, Tomas pradeda bėgti nuo langelio (n,n) iki langelio (1,1). Tomas iš langelio (i,j) gali judėti į langelį (i-1,j) arba (i,j-1). Nei Tomas nei Jonas negali išbėgti iš kvadrato ribų.

Norint laimėti estafetę, reikia surinkti kiek įmanoma daugiau taškų. Komandos taškai, tai visų Tomo bei Jono aplankytų langelių skaičių suma. Kiekvienas langelis į sumą įskaičiuojamas tik vieną kartą.

Jūsų užduotis, rasti maksimalų Jono ir Tomo komandos taškų skaičių.

Pradiniai duomenys

Pirmoje eilutėje yra skaičius n (1\\leqn\\leq300).

Sekančiose n eilučių yra po n skaičių: i-tojoje eilutėje esantis j-tasis skaičius a_(i,j) (-1000\\leqa_(i,j)\\leq1000), tai skaičius užrašytas langelyje (i,j).

Rezultatai

Išveskite vieną skaičių - kiek daugiausia taškų gali surinkti Jonas bei Tomas.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
3
25 16 25
12 18 19
11 13 8
 
136