Ion este
patronul unei firme de succes. Datorita dinamismului activitatii din firma,
fiecare angajat are un telefon mobil, cu care el poate comunica cu ceilalti
angajati.
Ion plateste factura telefonica pentru toti angajatii firmei si încearca
sa mai reduca din cheltuieli.
Recent a descoperit serviciul telefonic “friends” care ar putea reduce
substantial costurile în anumite conditii. Doua persoane care îsi
telefoneaza frecvent se declara pereche friends si utilizând
acest serviciu pot plati mai putin pentru convorbirile pe care le au între
ei. Evident, toate celelalte convorbiri se platesc la tarif normal. O persoana
poate sa apartina unei singure perechi friends.
Ion analizeaza acum lista convorbirilor angajatilor sai din ultima luna si încearca
sa stabileasca perechi friends astfel încât costul total
al facturilor telefonice sa fie cât mai mic.
Cerinta
Scrieti un program care determina costul total minim care se poate obtine pentru
o lista de convorbiri data utilizând serviciul friends.
Date de
intrare
Fisierul de intrare friends.in
contine pe prima linie doua numere naturale F
si R separate printr-un spatiu
(F reprezinta costul pentru un
minut de conversatie în regim friends, iar R
reprezinta costul unui minut de conversatie în regim normal). Pe cea de
a doua linie se afla numarul natural N
care reprezinta numarul de angajati din firma. Pe cea de a treia linie este
scris un numar natural C care
reprezinta numarul total de convorbiri. Pe fiecare dintre urmatoarele C
linii se afla informatii despre convorbirile dintre angajatii firmei, câte
o convorbire pe o linie. Pentru o convorbire sunt specificate trei numere naturale
separate prin câte un spatiu x
y d cu semnificatia „angajatul x
a sunat pe angajatul y, convorbirea
durând d minute”.
Date de
iesire
Fisierul de iesire friends.out
va contine o singura linie pe care va fi scris costul total minim care se poate
obtine pentru lista de convorbiri data utilizând serviciul friends.
Restrictii
1 <= F <= R <= 100
2 <= N < 15
1 <= C <= 10000
1 <= d <= 100
Angajatii sunt numerotati de la 1
la N.
Exemple
friends.in
friends.out
Explicatie
friends.in
friends.out
Explicatie
1
2
4
4
2 3 18
2 4 26
2 3 2
1 4 12
84
Costul
84 se poate obtine declarând perechile friends 1, 4 si 2,
3.
3
10
6
4
1 3 50
3 5 85
4 1 87
2 3 73
1746
Costul
1746 se poate obtine declarând perechile friends 1, 4; 2,
6 si 3, 5.