Enunț

Trei copii au inventat un joc nou care se joaca în trei. 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:
- 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 pot să sară doar în cercuri situate î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;
- punctajul obţinut de un concurent este obtinut 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ța

Să se determine: 1) punctajul maxim pmax pe care îl poate obţine un concurent la finalul jocului;
2)valoarea cercului iniţial vcerc al concurentului care va obţine punctajul maxim.

Date de intrare

Fișierul de intrare joc10.in conține două linii.Pe prima linie este scris numărul 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ţ.

Date de ieșire

Fișierul de ieșire joc10.out conţine pe prima linie pmax iar pe a doua linie vmax.

Restricții și precizări

• 2 ≤ N ≤ 135
• 1 ≤ x1, x2 ,…, 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.

Exemplu:

joc10.in

3
10 4 3 11 14 2 9 6 5 7

joc10.out

37
7

Explicație

Punctajele maxime care pot fi obținute de concurenți sunt: copilul din A va aduna 34 (=10+4+11+9); cel din B va aduna 37 (=9+11+14+3) iar cel din C va aduna 37 (=7+5+14+11). Astfel pmax=37 iar vmax=7.