Fermerio Bilo uždavinys

Pradinių duomenų failas:

fermeris.in  

Rezultatų failas:

fermeris.out  

Laiko apribojimas:

2 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Sklando gandai, kad Žemę dažnai aplanko Neatpažinti Skraidantys Objektai (NSO). Kartais NSO nusileidžia, ir toje vietoje išdegina žemės plotus. Stebėjimai rodo, kad šie plotai būna apskritimo formos.

Neseniai fermeris Bilas rado tokius apskritimus savo kviečių lauke. Bilui labai patinka visi paslaptingi dalykai, todėl jis nusprendė palikti lauke šias žymes. Tačiau, nors Bilas ir yra NSO mėgėjas, pirmiausia jis – fermeris, ir jam reikia pjauti savo kviečius. Todėl jis nusprendė neliesti plotų, kuriuose yra apskritimai, ir nupjauti kviečius visame likusiame plote. Visi plotai, kurių Bilas nepjaus, turi būti stačiakampiai, kurie vienas kito neliečia ir nepersidengia. Šių stačiakampių kraštinės turi būti lygiagrečios lauko kraštams. Visi NSO palikti apskritimai turi būti šiuose stačiakampiuose, o jų bendras plotas turi būti minimalus, kad Bilas galėtų nupjauti kviečius kuo didesnėje lauko dalyje.

Bilas norėtų sužinoti, kokiame plote jis galės nupjauti kviečius. Padėkite jam!

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje įrašyti du sveikieji skaičiai x ir y – fermerio Bilo lauko ilgis ir plotis (1 ≤ x, y ≤ 1000). Tarsime, kad Bilo laukas yra stačiakampis plokštumoje, kurio viršunės yra koordinatėse (0, 0), (x, 0), (x, y) ir (0, y).

Antroje eilutėje įrašytas sveikas skaičius N – apskritimų, kuriuos Bilo lauke paliko NSO, skaičius (0 ≤ N ≤ 100). Kitos N eilučių aprašo šiuos apskritimus: kiekvienoje eilutėje įrašyti trys sveikieji skaičiai \(x_{i}\), \(y_{i}\) ir \(r_{i}\) – apskritimo centro koordinatės ir apskritimo spindulys. Šie apskritimai gali liestis, kirstis arba būti vienas kitame. Visi apskritimai visiškai priklauso fermerio Bilo laukui.

Rezultatai

Jūsų programa turi išvesti vienintelį skaičių – Bilo lauko dalies, kurioje jis galės nupjauti kviečius, plotą.

Pavyzdžiai

10 8
2
4 4 2
6 4 1

60

10 8
2
3 3 1
1 1 1

64