grup

Ion este managerul unei firme de succes. Datorita dinamismului activitatii din firma, fiecare angajat trebuie sa aiba un telefon mobil, cu care el sa poata comunica cu ceilalti angajati ai firmei. Ion plateste factura telefonica pentru toti angajatii si încearca sa reduca din cheltuieli.
Recent a descoperit serviciul telefonic "grup" care ar putea reduce substantial costurile în anumite conditii. Mai exact, Ion poate selecta un grup de k angajati si activând serviciul grup pentru cei k angajati selectati, ei vor plati cu 50% mai putin pentru convorbirile pe care le au cu membrii grupului, celelalte convorbiri fiind taxate la tarif normal. Daca un angajat din grup suna un alt membru al grupului el va plati 10 bani/minut. Pentru orice alta convorbire tariful normal este de 20 bani/minut. Taxarea convorbirilor se realizeaza la minut.
Ion analizeaza acum lista convorbirilor angajatilor sai din ultima luna si încearca sa stabileasca grupul astfel încât costul total al facturilor telefonice sa fie cât mai mic.

Cerinta

Scrieti un program care determina un grup de k angajati astfel încât, utilizând serviciul grup, costul total al convorbirilor telefonice sa fie minim.

Date de intrare

Fisierul de intrare grup.in continepe prima linie numarul natural k reprezentând numarul de angajati care trebuie sa formeze grupul. Pe cea de a doua linie se afla numarul natural N care reprezinta numarul total de convorbiri din lista de convorbiri ale angajatilor firmei. Pe fiecare dintre urmatoarele N linii se afla informatii despre convorbirile dintre angajatii firmei, câte o convorbire pe o linie. Pentru o convorbire sunt specificate:
nume1 nume2 d
cu semnificatia "angajatul nume1 a sunat pe angajatul nume2, convorbirea durând d minute".

Date de iesire

Fisierul de iesire grup.out va contine pe prima linie costul total minim al convorbirilor telefonice exprimat în bani. Pe urmatoarele k linii sunt scrise numele angajatilor care formeaza grupul, câte un nume pe o linie.

Restrictii si precizari

• 1 <= k <= numarul de angajati din firma <= 20
• 1 <= N <= 1000
• 1 <= d <= 100
• Numele angajatilor au maxim 20 caractere (litere mari ale alfabetului englez).
• Daca exista mai multe solutii, afisati oricare dintre ele.
• Ordinea în care sunt scrise numele angajatilor din grup nu conteaza.
• Pentru determinarea costului minim se va acorda 40% din punctaj. Pentru un cost minim corect si afisarea corecta si completa a grupului de k persoane care asigura costul minim se acorda 100% din punctaj.
  

Exemple

Timp maxim de executie/test: 0.15 secunde

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com