Fie o matrice cu N linii şi N coloane de numere naturale. Liniile şi coloanele sunt numerotate de la 1 la N. Se doreşte traversarea matricei pe un drum pornind din poziţia (1, 1) în (N, N), mergând pas cu pas. La un pas, de la o poziţie (i, j) se poate trece într-una din poziţiile (i+1, j), (i+1, j+1), (i, j+1). Costul drumului este dat de suma valorilor componentelor care fac parte din drum.
Cerinţă
Scrieţi un program care determină un drum de cost maxim de la poziţia (1, 1) la (N, N) şi cu proprietatea că acest cost maxim este multiplu de 3.
Date de intrare
Fisierul de intrare maxtri.in conţine pe prima linie un număr natural N, iar pe următoarele N linii se află câte N numere naturale separate prin câte un spaţiu reprezentând valorile de pe o linie din matrice.
Date de ieşire
Fisierul de iesire maxtri.out va conţine un singur număr natural reprezentând costul maxim divizibil cu 3 al unui drum de la poziţia (1, 1) la (N, N). Dacă nu există niciun drum de cost divizibil cu 3, se va afişa valoarea 0.
Restricţii
1 <= n <= 500
Elementele matricei sunt numere naturale cuprinse între 1 şi 10 000
Exemple
maxtri.in
maxtri.out
Explicaţii
3
2 3 1
5 6 7
9 8 4
24
Drumul de cost maxim trece prin componentele de coordonate (1,1) (2,1) (2,2) (2,3) (3,3). Costul său este 2+5+6+7+4 = 24, iar 24 este divizibil cu 3.
De remarcat că există drumuri de cost mai mare, dar care nu sunt divizibile cu 3.
maxtri.in
maxtri.out
Explicaţii
3
1 3 3
3 3 3
3 3 3
0
Nu există niciun drum de la (1,1) la (3,3) de cost divizibil cu 3.