Ionel si Gigel s-au hotarât să-şi amintească jocul din copilărie numit „Maroco”. Ei au la dispoziţie beţişoare, numerotate de la la . Fiecare beţişor are un anumit punctaj, punctajele fiind distincte. La început beţişoarele sunt aranjate într-o grămadă, în care beţisoarele sunt suprapuse.
Regulile jocului sunt:
- la un moment dat nu poate fi extras decât un singur beţişor care este „liber”, adică nu are alt beţişor deasupra lui;
- copiii nu gândesc mai multe mutări înainte, ci aleg cea mai bună mişcare de la pasul respectiv, adică aleg beţişorul „liber” cu punctajul cel mai mare.
Jocul este început de către Ionel.
Cerință
Cunoscând numărul de beţişoare , punctajul fiecărui beţişor şi modul de aşezare a beţişoarelor în grămadă, determinaţi care dintre copii este câştigător şi ce punctaj a acumulat.
Date de intrare
Fişierul de intrare maroco.in
conţine pe prima linie numărul de beţişoare . Pe următoarele linii se află informaţii despre cele beţişoare. Mai exact, linia conţine: , unde este punctajul beţişorului , este numărul de beţişoare aflate peste beţişorul , iar este lista celor beţişoare aflate iniţial peste beţişorul .
Numerele scrise pe aceeaşi linie sunt separate prin spaţii.
Date de ieșire
Fişierul de ieşire maroco.out
conţine pe prima linie două numere naturale separate prin spaţiu și , unde reprezintă câştigătorul jocului ( dacă Ionel este câştigătorul, dacă Gigel este câştigătorul sau în caz de egalitate), iar reprezintă punctajul total acumulat de câştigător.
Restricții și precizări
- și este par.
- Toate numerele care intervin în problemă sunt numere naturale.
- Pentru datele de test există întotdeauna soluţie.
Exemplu
maroco.in
10
70 0
100 3 1 9 10
40 2 2 4
80 2 1 6
90 2 2 7
40 0
60 2 6 9
20 1 10
10 1 8
50 0
maroco.out
1 320
Explicație
Beţişoarele alese de fiecare copil sunt:
- Ionel: (p), (p), (p), (p), (p) p;
- Gigel: (p), , (p), (p), (p), (p) p.