Cerința

O tablă de șah se reprezintă ca o matrice cu n linii și n coloane în care pozițiile libere au valoarea 0, iar pozițiile ocupate de piese sunt marcate prin valoarea 1.

Să se determine numărul maxim de piese pe care le poate lua un pion care pleacă de pe prima linie a tablei și vrea să ajungă pe ultima linie. Pionul poate porni din orice poziție de pe prima linie. Pe prima linie nu se află alte piese.

Pionul aflat în pozitia i,j se poate deplasa astfel:

• în poziția i+1, j dacă este liberă
• în poziția i+1, j-1 dacă este o piesă în această poziție
• în poziția i+1, j+1 dacă este o piesă în această poziție

Date de intrare

Programul citește de la tastatură numărul n, reprezentând dimensiunea tablei, iar apoi n*n numere 0 sau 1 cu semnificația din enunț.

Date de ieșire

Programul va afișa pe ecran numărul x, reprezentând numărul maxim de piese pe care le poate lua pionul.

Restricții și precizări

• 1 ≤ n ≤ 100

Exemplu:

Intrare

5
0 0 0 0 0
0 1 0 1 0
0 1 1 1 1
0 0 0 1 1
0 1 0 1 1

Ieșire

4

Explicație

Pionul poate lua maximum 4 piese, pe traseul (1,1) (2,2) (3,3) (4,4) (5,5). Acest traseu nu este unicul pe care pionul poate lua 4 piese.