maroco

Time limit: 0.02s Memory limit: 4MB Input: maroco.in Output: maroco.out

Ionel si Gigel s-au hotarât să-şi amintească jocul din copilărie numit „Maroco”. Ei au la dispoziţie nn beţişoare, numerotate de la 11 la nn. 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 nn, punctajul fiecărui beţişor p1,p2,,pnp_1, p_2, \dots, p_n ş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 nn. Pe următoarele nn linii se află informaţii despre cele nn beţişoare. Mai exact, linia i+1i+1 conţine: pi nri bi1 bi2  bnrip_i \ nr_i \ b_{i_1} \ b_{i_2}\ \dots\ b_{nr_i}, unde pip_i este punctajul beţişorului ii, nrinr_i este numărul de beţişoare aflate peste beţişorul ii, iar bi1 bi2  bnrib_{i_1} \ b_{i_2}\ \dots\ b_{nr_i} este lista celor nrinr_i beţişoare aflate iniţial peste beţişorul ii.

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 ww și tt, unde ww reprezintă câştigătorul jocului (11 dacă Ionel este câştigătorul, 22 dacă Gigel este câştigătorul sau 00 în caz de egalitate), iar tt reprezintă punctajul total acumulat de câştigător.

Restricții și precizări

  • 2n1002 \leq n \leq 100 și nn este par.
  • 1pi1 0001 \leq p_i \leq 1 \ 000
  • 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: 11 (7070p), 66 (4040p), 88 (2020p), 22 (100100p), 55 (9090p) 320\rightarrow 320p;
  • Gigel: 1010 (5050p), 44, (8080p), 99 (1010p), 77 (6060p), 33 (4040p) 240\rightarrow 240p.

Log in or sign up to be able to send submissions!