culmi

Dornic de o condiţie fizică perfectă, un viitor olimpic naţional la informatică îşi propune să escaladeze cea mai înaltă culme a unui un masiv muntos. Se echipează corespunzator, îşi cumpără un termos, îl umple cu apă, culege informaţiile despre traseele existente şi completează astfel fişierul de intrare popas.in. Pe parcursul fiecărui traseu există mai multe izvoare de la care drumeţul îşi poate umple termosul. Ştiind că pe munte este bine să mergi cu pas constant şi fără ruperi de ritm, îşi propune să atingă culmea facând cât mai puţine popasuri (pentru umplerea termosului).

Cerință

Dintre toate traseele existente către culme determinaţi-l pe cel pentru care numărul total de popasuri este minim. Dacă sunt mai multe astfel de trasee, se va alege cel care este scris ultimul în fişierul de intrare.

Date de intrare

Fişierul popas.in conţine:

• pe prima linie, $k$ - numărul total de trasee către culme
• pe fiecare dintre următoarele $k$ linii descrierea câte unui traseu (pe fiecare linie numerele sunt separate prin câte un spaţiu), adică:
  • $i$ - numărul asociat traseului (fiecare traseu este identificat în mod unic printr-un număr natural cuprins între $1$ şi $k$)
  • $r$ - numărul izvoarelor cu apă rece de pe traseu
  • $d_1, d_2, \dots, d_r$ – $r$ numere reprezentând distanţa de la punctul de plecare până la fiecare izvor
• pe ultimele două linii:
  • t distanţa pentru care drumeţului îi este suficientă apa din termos
  • u distanţa pe care drumeţul o poate străbate fără apă

Date de ieșire

Fişierul popas.out va conţine pe aceeasi linie, despărţite prin spaţiu, două numere: primul reprezintă numărul minim de popasuri necesare deplasarii şi al doilea numărul traseului ales. Dacă problema nu are soluţie fişierul de ieşire va conţine cifra $0$.

Restricții și precizări

• În fişierul de intrare toate distanţele sunt exprimate în kilometri
• Pentru fiecare traseu distanţa dintre ultimul izvor (cel mai îndepărtat de punctul de plecare) şi culme este de $1$ kilometru
• $0 < k \leq 100$;
• $0 < r \leq 20$;
• $0 < di \leq 360$;
• $1 \leq t \leq 10$;
• $1 \leq u \leq 5$;

Exemplul 1

popas.in

3
2 3 12 5 9
1 4 2 9 7 11
3 5 2 16 7 9 8
6
2

popas.out

1 1

Exemplul 2

popas.in

2
1 3 12 5 9
2 3 2 7 11
1
2

popas.out

0