Enunț

Un muzeu al diamantelor își are sediul într-o clădire cu formă cubică cu N etaje, numerotate de la 1 la N. Suprafața fiecărui etaj K (1 ≤ K ≤ N) este pătratică și este împărțită în N * N camere identice alăturate, dispuse pe N linii și N coloane, etichetate fiecare cu câte trei numere K L C (K = etajul, L= linia, C = coloana, 1 ≤ L, C ≤ N) ca în imaginea de mai jos.

În fiecare cameră se află câte un diamant veritabil, cu valoarea cunoscută. Mulți hoți râvnesc la aceste diamante! Așa că… s-au apucat să studieze cu mare atenție planul clădirii.

Ei au aflat că intrarea în clădire se face prin camera cu eticheta 1 1 1 și că din fiecare cameră cu eticheta K L C a clădirii se poate intra în cel mult trei camere:

• camera cu eticheta K L C+1, dacă C < N
• camera cu eticheta K L+1 C, dacă L < N
• camera cu eticheta K+1 L C, dacă K < N

Hoții au descoperit că din camera cu eticheta N N N se ajunge direct pe acoperișul clădirii unde se află un elicopter gata de zbor (cu el vor pleca). Ei trebuie să aleagă cel mai profitabil traseu care să pornească din camera cu eticheta 1 1 1 și să ajungă în camera cu eticheta N N N și care, bineînțeles, să le permită să obțină o sumă maximă din vânzarea diamantelor furate din camerele prin care au trecut în traseu ales.

Cerințe

Cunoscându-se numărul N și valoarea de vânzare a fiecărui diamant din cele N*N*N camere, să se determine:

a) numărul D de diamante furate de hoți din camerele parcurse în traseul ales;
b) suma maximă S pe care o vor obține din vânzarea diamantelor furate;
c) etichetele camerelor prin care trece traseul ales, în ordinea în care sunt parcurse camerele.

Date de intrare

Fișierul de intrare smax.in conține pe prima linie numărul N, iar pe a doua linie N*N*N numere naturale separate prin câte un spațiu, reprezentând valoarea de vânzare a fiecărui diamant din fiecare cameră, în ordinea lexicografică a etichetelor camerelor.

Date de ieșire

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

• pe prima linie numărul D, reprezentând numărul diamantelor furate de hoți (răspunsul la cerința a);
• pe a doua linie, fișierul va conține un număr natural S reprezentând suma maximă (răspunsul la cerința b);
• pe fiecare din următoarele D linii, se vor scrie câte trei numere naturale X Y Z, separate prin câte un spaţiu, reprezentând etichetele camerelor prin care trece traseul ales de hoți, în ordinea în care sunt parcurse camerele (răspunsul la cerința c).

Restricții și precizări

• 3 ≤ N ≤ 100
• Valoarea de vânzare a fiecărui diamant este un număr natural nenul cel mult egal cu 100.
• Dacă suma maximă S se poate obține pentru mai multe trasee, atunci traseul scris în fișierul smax.out va fi cel mai mic traseu din punct de vedere lexicografic.
• Se acordă: 20% din punctaj pentru cerința a); 20% din punctaj pentru cerinta b) și 60% din punctaj pentru cerința c).

Exemplu:

smax.in

3
1 2 5 2 3 1 4 1 2 2 1 1 1 2 2 1 1 1 1 4 2 1 3 1 1 1 2

smax.out

7
14
1 1 1
1 1 2
1 1 3
1 2 3
1 3 3
2 3 3
3 3 3

Explicație

Clădirea are trei etaje (1,2 şi 3). Pe fiecare etaj sunt 3*3 camere. Hoții vor fura D=7 diamante, suma maximă obținută fiind S=14. Traseul va trece prin 7 camere. Sunt mai multe trasee pentru care se poate obține suma maximă, de exemplu:
1) (1 1 1, 1 1 2, 1 1 3, 1 2 3, 1 3 3, 2 3 3, 3 3 3)
2) (1 1 1, 1 1 2, 1 1 3, 1 2 3, 2 2 3, 2 3 3, 3 3 3)
3) (1 1 1, 1 1 2, 1 1 3, 1 2 3, 2 2 3, 3 2 3, 3 3 3)
4) (1 1 1, 1 1 2, 1 1 3, 2 1 3, 2 2 3, 3 2 3, 3 3 3)
5) (1 1 1, 2 1 1, 3 1 1, 3 1 2, 3 2 2, 3 3 2, 3 3 3)
6) (1 1 1, 1 1 2, 2 1 2, 3 1 2, 3 2 2, 3 3 2, 3 3 3)
7) (1 1 1, 1 1 2, 1 2 2, 2 2 2, 3 2 2, 3 3 2, 3 3 3) etc.