== include(page="template/taskheader" task_id="joc9") ==

Poveste şi cerinţă...

   Trei copii au inventat un joc nou. Ei au desenat pe asfalt un triunghi echilateral $ABC$ şi l-au împărţit în $N*N$ triunghiuri echilaterale congruente. Pornind din vârful $A$ al triunghiului $ABC$ către latura opusă $BC$, au desenat   cercuri identice, câte unul în fiecare vârf al triunghiurilor formate, iar în interiorul fiecărui cerc au scris câte un număr natural nenul reprezentând valoarea cercului, ca în figura alăturată desenată pentru $N$=3.
 
Copiii au stabilit regulamentul de desfăşurare a  jocului:
 
* la joc pot participa doar trei concurenţi;
* fiecare concurent se aşează într-unul din cercurile situate în vârfurile $A$, $B$ sau $C$ ale triunghiului, denumite cercuri iniţiale;
* fiecare concurent trebuie să ajungă într-unul din cele n+1 cercuri situate pe latura opusă vârfului din care a plecat, în triunghiul $ABC$, şi poate să se deplasaze doar în direcţia acestei laturi; de exemplu, dacă un concurent se află în cercul iniţial din vârful $C$, el trebuie să ajungă într-unul din cercurile cu valorile: $x1$, $x2$, $x4$ sau $x7$  de pe latura opusă, $AB$;
* concurenţii se vor deplasa sărind dintr-un cerc în altul, fără a trece de mai multe ori prin acelaşi cerc;
* este permis ca într-un cerc să se afle mai mulţi concurenţi;
* la fiecare secundă, simultan, concurenţii trebuie să sară într-unul din cercurile situate la cea mai mică distanţă de cel în care se află, în direcţia laturii opuse corespunzătoare; de exemplu, un concurent, care a plecat din cercul iniţial situat în vârful $B$ şi care se află în cercul cu valoarea  $x5$, poate sări doar în unul din cercurile cu valorile $x3$ sau $x6$;
* concurenţii nu au voie să sară într-un cerc care nu se află în direcţia laturii opuse corespunzătoare;
* jocul se termină atunci când concurenţii ajung într-unul din cele n+1 cercuri situate pe latura cerută din triunghiul $ABC$, prin efectuarea a câte n sărituri, fiecare;
* pentru fiecare concurent, se va calcula punctajul obţinut prin adunarea valorii cercului iniţial cu valorile celor n cercuri, în care a sărit în timpul deplasării;
* câştigătorul jocului este concurentul cu cel mai mare punctaj; pot fi mai mulţi câştigători dacă sunt mai mulţi concurenţi care au obţinut un punctaj egal cu cel mai mare punctaj obţinut la finalul jocului.
Cerinţe.
 
h2. Cerinta
 
Să se scrie un program care să determine:
a)	punctajul maxim pe care îl poate obţine un concurent la finalul jocului;
b)	valoarea cercului iniţial din care un concurent ar trebui să înceapă jocul pentru a obţine punctajul maxim.
 
 

h2. Date de intrare

Fişierul de intrare $joc9.in$ ...

Fişierul de intrare $joc9.in$  conţine două linii. Pe prima linie este scris numărul natural nenul n. Pe a doua linie sunt scrise   numere naturale nenule: x1,x2,...,x(n+1)*(n+2)/2, separate prin câte un spaţiu, reprezentând valorile cercurilor din joc, în ordinea din enunţ

h2. Date de ieşire

În fişierul de ieşire $joc9.out$ ...

Fişierul de ieşire $joc9.out$ va conţine două linii. Pe prima linie se va scrie un număr natural reprezentând punctajul maxim pe care îl poate obţine un concurent la finalul jocului. Pe a doua linie se va scrie un număr natural reprezentând valoarea cercului iniţial din care un concurent ar trebui să înceapă jocul pentru a obţine punctajul maxim.

h2. Restricţii

* $... ≤ ... ≤ ...$

* {$2 ≤ N ≤ 135$}
* {$1 ≤ x{~1~},x{~2~},…,x{~(n+1)*(n+2)/2~} ≤ 215$}
* Dacă există mai multe variante de alegere a cercului iniţial, se va scrie în fişier cea mai mică dintre valorile acestor cercuri iniţiale din care se obţine punctajul maxim.
* Pentru rezolvarea cerinţei a) se acordă 70% din punctaj şi pentru cerinţa b) 30% din punctaj.
 

h2. Exemplu
table(example). |_. joc9.in |_. joc9.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|3
10 4 3 11 14 2 9 6 5 7
|37
7
|

h3. Explicaţie

...

Dacă concurentul pleacă din cercul iniţial din vârful:
- A, cel mai mare punctaj pe care îl poate obţine este 34  (=10+4+11+9)
- B, cel mai mare punctaj pe care îl poate obţine este 37 (=9+11+14+3)
- C, cel mai mare punctaj pe care îl poate obţine este 37 (=7+5+14+11).
Astfel, punctajul maxim este 37 şi se poate obţine dacă concurentul pleacă din cercurile  iniţiale din B şi C. Cercul din B are valoarea 9, iar cel din C are valoarea 7<9. Pe prima linie a fişierului joc.out se va scrie valoarea 37 (punctajul maxim), iar pe a doua linie se va scrie valoarea 7 (cercul iniţial din C are valoarea mai mică decât cel din B)
 

== include(page="template/taskfooter" task_id="joc9") ==