Dornic de o condiţie fizică perfectă, un viitor olimpic naţional la informatică îşi propune să escaladeze cea mai înaltă culme a unui masiv muntos. Se echipează corespunzător, îş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;
- d1,d2,…,dr – 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 prima linie, despărţite prin spaţiu, două numere: primul reprezintă numărul minim de popasuri necesare deplasării ş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
0<k<=100
0<r<=20
0<di<=360
1<=t<=10
1<=u<=5
Î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.
Datele de intrare sunt corecte (nu necesită validare).