Terenuri 3D

Time limit: 0.06s Memory limit: 64MB Input: terenuri3d.in Output: terenuri3d.out

“Iarba din curtea vecinului este întotdeauna mai verde ...”

Î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)(x, y, z) cu semnificaţia : ţăranul xx ar avea gradul de fericire zz dacă ar locui în casa yy. 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 00.

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 NN şi MM reprezentând numărul ţăranilor, respectiv numărul caselor din Gheorgheni, precum şi KK triplete de forma (x,y,z)(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)(A, B) cu semnificaţia: ţăranul AA primeşte casa BB.

Date de intrare

Fişierul de intrare terenuri3d.in va conţine pe prima linie trei numere N,MN, M şi KK cu semnificaţia din enunţ. Următoarele KK linii vor conţine câte trei numere x,y,zx, 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 GG reprezentând gradul maxim de fericire. Pe linia a doua se va afla un număr PP reprezentând numărul de ţărani care vor primi o casă dintre cele dorite, iar pe următoarele PP linii se vor afla perechile de numere A,BA, B separate printr-un spaţiu cu semnificaţia din enunţ.

Restricţii şi precizări

  • N,M250N, M ≤ 250
  • K1 000K ≤ 1 \ 000
  • gradul maxim de fericire 30 000≤ 30 \ 000

Exemplu

terenuri3d.in

2 2 3
1 1 1
2 2 2
1 2 10

terenuri3d.out

10
1
1 2	

Explicaţie

Ţăranul 11 va primi casa 22, iar ţăranul 22 nu va fi satisfăcut. Gradul total de fericire din sat va fi 1010. Nicio altă imparţire nu va genera un grad de fericire mai mare.

Log in or sign up to be able to send submissions!