Monica s-a angajat ca administrator de retea si nu e o misiune prea usoara. Reteaua de calculatoare pe care o administreaza este formata din N calculatoare (numerotate de la 1 la N). O conexiune directa in retea este un cablu care leaga doua calculatoare distincte si asigura comunicarea bidirectionala intre cele doua calculatoare conectate. In retea exista M conexiuni directe. Evident, conexiunile directe existente asigura comunicarea in retea (adica oricare doua calculatoare in retea pot comunica - direct sau indirect, prin intermediul altor calculatoare).
Monica intentioneaza sa protejeze pe cat posibil cablurile de retea. In primul rand ea va selecta doar o parte dintre cele M conexiuni directe astfel incat comunicarea in retea sa fie in continuare asigurata de conexiunile selectate, iar suma lungimilor cablurilor sa fie cat mai mica. Monica numeste aceste conexiuni selectate conexiuni minimale.
Seful Monicai, Ionel i-a furnizat masca protectoare de lungime K metri. Monica poate taia bucati din masca protectoare astfel incat sa protejeze cablurile care realizeaza conexiunile minimale (un cablu va fi protejat integral - pe toata lungimea lui - sau deloc).

Numim operatia de alegere a unei submultimi de conexiuni minimale si imbracarea lor in masca protectoare pe toata lungimea lor "mascare". Doua "mascari" se considera distincte daca difera prin consumul total de masca protectoare utilizata. Evident consumul total al unei mascari nu poate depasi K (numarul de metri de masca disponibili).

Monica doreste ca sa selecteze conexiunile minimale astfel incat numarul de mascari distincte sa fie maxim.

Cerinţă

Scrieti un program care sa determine suma lungimilor conexiunilor minimale, precum si numarul maxim de mascari distincte ale acestora.

Date de intrare

Fisierul de intrare retea.in contine pe prima linie numerele naturale N, M si K, avand semnificatia din enunt. Urmeaza apoi M linii, pe fiecare linie aflandu-se trei numere naturale a, b si c reprezentand faptul ca exista o conexiune directa intre calculatoarele a si b, lungimea cablului fiind c metri.

Date de ieşire

Fisierul de iesire retea.out va contine o singura linie pe care vor fi scrise doua numere naturale separate prin spatiu. Primul numar reprezinta suma lungimilor conexiunilor minimale selectate (minima posibil). Al doilea numar reprezinta numarul maxim de mascari distincte ale conexiunilor minimale.

Restricţii

• 1 <= N <= 1000
• 1 <= M <= 20000
• 1 <= K <= 50000
• 1 <= a, b <= N, a != b
• 1 <= c <= 50000
• Intre doua calculatoare pot exista mai multe conexiuni directe.
• Daca numai suma lungimilor conexiunilor minimale este calculata corect se acorda 30% din punctajul pe test.

Exemple

retea.in	retea.out	Explicatie
4 4 5 1 2 1 2 3 1 3 4 1 3 4 3	3 4	Singura multime de conexiuni minimale pe care oputem alege este {1-2, 2-3, 3-4}, acesta avand suma lungimilor 3, cea mai mica posibila cu proprietatea ca oricare doua calculatoare pot comunica. Pentru aceasta multime de conexiuni minimale exista 4 mascari distincte, avand consumul total de masca protectoare 0, 1, 2, respectiv 3. De exemplu pentru mascare cu consumul 1 se poate imbraca in masca protectoare oricare conexiune minimala selectata. Pentru consumul 2 se pot imbraca in masca protectoare oricare doua conexiuni minimale selectate. Pentru consumul 3 se vor imbraca in masca protectoare toate cele 3 conexiuni minimale. Evident, pentru consumul 0 nu vom imbraca in masca protectoare nici o conexiune.

stud. Adrian Airinei

Facultatea de Informatica Iasi

emanuela.cerchez@gmail.com