Bogdănel a primit cadou o trusă de geometrie. Categoric, cel mai interesant i s-a părut compasul. Aşa că acum face cercuri peste tot, inclusiv pe perete.
Tatăl său încearcă să găsească repede o soluţie, să acopere cercurile desenate pe perete înainte de a veni mama lui Bogdan acasă.
Peretele are L metri lungime şi H metri înălţime. Pe perete, tatăl lui Bogdan şi-a imaginat un sistem de coordonate, cu colţul în stânga-jos, astfel că poate identifica cercurile desenate de Bogdan prin coordonatele centrului şi raza. Tatăl lui Bogdan intenţionează să acopere zonele desenate de Bogdan cu afişe astfel:

• afişele au formă dreptunghiulară şi vor fi plasate cu laturile paralele cu laturile peretelui
• afişele nu trebuie să se suprapună (nici măcar să se atingă)
• afişele trebuie să acopere toate cercurile desenate de Bogdan.
• suma ariilor zonelor acoperite de afişe să fie minimă.

Cerinţă

Scrieţi un program care să determine suma minimă a ariilor zonelor acoperite de afişe.

Date de intrare

Fişierul de intrare afise.in conţine pe prima linie două numere naturale L şi H, separate prin spaţiu, reprezentând dimensiunile peretelui. Pe cea de a doua linie se află un număr natural N, reprezentând numărul de cercuri desenate. Pe următoarele N linii sunt descrise cercurile, câte un cerc pe o linie, specificând 3 numere naturale separate prin spaţiu xc yc rc, reprezentând în ordine abscisa centrului, ordonata centrului şi raza cercului.

Date de ieşire

Fişierul de ieşire afise.out va conţine o singură linie pe care va fi scrisă suma minimă a ariilor zonelor acoperite de afişe.

Restricţii

• 1 <= L, H <= 1000
• 1 <= N <= 100
• Toate cercurile sunt desenate complet pe perete.

Exemple

afise.in	afise.out
10 8 2 4 4 2 6 4 1	20
afise.in	afise.out
10 8 2 3 3 1 1 1 1	16

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com