Împărţirea recentă a terenurilor din Gheorgheni a generat multă invidie în rândul ţăranilor. Astfel, unii ţărani au impresia că iarba creşte mai verde în curtea unora dintre vecini şi ar dori să se mute într-una din casele acestora. Primaria Gheorgheni a hotărât o redistribuire a proprietăţilor astfel încât gradul total de fericire al ţăranilor să fie cât mai mare.
Redistribuirea se va face ţinând cont de preferinţele ţăranilor pentru anumite case şi de gradul de fericire al fiecărui ţăran, în funcţie de casa în care ar fi repartizat. Vor exista astfel triplete (x, y, z) cu semnificaţia: ţăranul x ar avea gradul de fericire z dacă ar locui în casa y. Un ţăran va fi satisfăcut dacă în urma redistribuirii va primi una dintre proprietăţile râvnite. E posibil ca nu toţi ţăranii să poată fi satisfăcuţi, caz în care gradul de fericire al acestora va fi 0.
Primarul satului Gheorgheni v-ar recompensa cu 100 de puncte în cazul în care îl ajutati să obţină cel mai mare grad de fericire posibil în sat, adică suma gradelor de fericire a ţăranilor satisfăcuţi. În acest mod şi-ar asigura un nou mandat la următoarele alegeri.
Cerinţă
Dându-se N şi M reprezentând numărul ţăranilor, respectiv numărul caselor din Gheorgheni, precum şi K triplete de forma (x, y, z) cu semnificaţia de mai sus, se cere gradul maxim de fericire, numărul de ţărani satisfăcuţi după împărtire, precum şi toate perechile de forma (A, B) cu semnificaţia: ţăranul A primeşte casa B.
Date de intrare
Fişierul de intrare terenuri3d.in va conţine pe prima linie trei numere N M K cu semnificaţia din enunţ. Următoarele K linii vor conţine câte trei numere x y z cu semnificaţia din enunţ, separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire terenuri3d.out va conţine pe prima linie un număr întreg G reprezentând gradul maxim de fericire. Pe linia a doua se va afla un număr P reprezentând numărul de ţărani care vor primi o casă dintre cele dorite, iar pe următoarele P linii se vor afla perechile de numere A B separate printr-un spaţiu cu semnificaţia din enunţ.
Restricţii
• N, M ≤ 250
• K ≤ 1000
• gradul maxim de fericire ≤ 30000
Exemple
terenuri3d.in
terenuri3d.out
Explicaţii
2 2 3
1 1 1
2 2 2
1 2 10
10
1
1 2
Ţăranul 1 va primi casa 2, iar ţăranul 2 nu va fi satisfăcut. Gradul total de fericire din sat va fi 10. Nicio altă împărţire nu va genera un grad de fericire mai mare.