Un „FNI triunghiular" este o cladire care are sectiunea în forma
de triunghi echilateral, iar încaperile corespund unor triunghiuri echilaterale
de latura 1. Pe fiecare latura a cladirii exista exact N încaperi. În
fiecare încapere se gaseste câte un seif care contine o suma de
bani.
Un hot poate intra in cladire prin una dintre cele 3 incaperi care constituie varfurile triunghiului. Scopul hotului este, evident, de a "colecta" o suma cât mai mare de bani din seifurile
existente în camere. Fiecare camera are exact 3 usi, cate una pe fiecare latura. Astfel, dupa intrarea într-o camera, hotul ia suma de bani aflata in seiful camerei respective si apoi se poate deplasa in una dintre camerele alaturate (cele doua situate pe acelasi nivel sau in camera situata pe nivelul imediat urmator). Dar odata ce hotul a parasit o camera, usile acesteia se inchid automat si el nu mai poate reveni in camera din care a plecat. In plus, hotul se poate deplasa in cladire doar in ordinea nivelurilor (de la varful prin care a intrat catre baza).
Cerinta
Determinati suma maxima care poate fi colectata de hot precum si numarul minim de
încaperi prin care trece hotul pentru a colecta suma respectiva.
Date de intrare
Fisierul de intrare fni.in
contine: N
s1
s2 s3 s4
s5 s6 s7 s8 s9
...
sN(N-2) ... sN*N
Date de iesire
Fisierul de iesire fni.out
contine doua linii. Pe prima linie se va scrie suma maxima colectata, iar pe cea de a doua linie se va scrie numarul minim de încaperi
vizitate.
Restrictii
1 <= N <= 100
0 <= si <= 300, 1 <= i <= N*N
Exemplu
fni.in
fni.out
Semnificatie
3
1
8 10 40
5 11 13 19 9
102
7
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
