După ce în problema #Plata şi-a cumpărat biscuiţi, iar în problema #Maraton şi-a făcut temele, Costy s-a hotărât să meargă în vizită la prietenul său Paul. Și pentru că Paul este prietenul său cel mai bun, bineînţeles că nu se va duce cu mâna goala. Va trece pe la magazin şi îi va cumpăra un pachet de biscuiţi. Marea problemă a eroului nostru este oraşul rău famat, la fiecare intersecţie existând pericole. Oraşul are forma de două triunghiuri dreptunghice isoscele cu un vârf comun, ca în figura următoare:

C 
X X
X X X
X X X B
      X X
      X X X
      X X X P 

C – reprezintă poziţia iniţială a lui Costy, care se va afla mereu în colţul din stânga sus.
B – reprezintă poziţia magazinului, care se va afla mereu în vârful comun al celor 2
triunghiuri.
P – reprezintă poziţia lui Paul, care se va afla mereu în colţul din dreapta jos.

Cum spuneam, la fiecare intersecţie există pericole. O intersecţie X[i][j] reprezintă intersecţia străzii orizontale i, cu strada verticală j. Gradul de periculozitate al unei intersecţii este un număr întreg X[i][j]. Definim gradul unui drum ca fiind suma gradelor intersecţiilor ce compun acel drum.

Costy poate merge de la o intersecţie X[i][j], doar la o intersecţie X[i][j + 1] (în dreapta) sau X[i + 1][j](în jos).

Cerința

Ajutaţi-l pe Costy să ajungă la magazin, apoi la Paul, alegând un drum cu un grad minim de periculozitate.

Date de intrare

Fișierul de intrare vizita.in conține:

• Pe prima linie, un număr natural N reprezentând lungimea laturii unui triunghi(numărul de linii).
• Urmează N linii, fiecare linie i va conţine i numere pe linie reprezentând harta oraşului, de la Costy la magazin.
• Urmează N – 1 linii reprezentând al doilea triunghi(fără vârful comun).
• Pe linia i exista i + 1 numere reprezentând harta oraşului, de la magazin la Paul.

Date de ieșire

Fișierul de ieșire vizita.out va conține:

• Un număr întreg R reprezentând gradul minim de periculozitate al drumului parcurs de Costy, până la Paul.

Restricții și precizări

• -1 000 000 000 <= X[i][j] <= 1 000 000 000
• 1 <= N <= 1 000
• Atenţie la limita de memorie!!!

Exemplu:

vizita.in

3
2 
-1 4
3 2 0
10 -3
3 1 2

vizita.out

16

Explicație

2 
-1 4
 3 2 0
     10 -3
      3 1 2

Se alege drumul format din 2, -1, 3, 2, 0, 10, -3, 1, 2.