Fişierul intrare/ieşire:	radio.in, radio.out	Sursă	Romanian Open Contest, TIMUS 2001
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Radio

Pe suprafata Romaniei exista K statii radio pozitionate la coordonate si altitudini diferite. Fiecare dintre aceste statii are o anumita raza de transmisie, adica o distanta maxima pana la care poate trimite semnalul radio. Guvernul dorste sa amplaseze o antena radio undeva pe harta, in asa fel incat sa receptioneze semnalele tuturor celor K statii radio (adica distanta pana la fiecare statie radio sa fie mai mica sau egala cu raza de transmisie a statiei respective).

Harta Romaniei poate fi privita ca o matrice cu M linii si N coloane, unde valoarea de pe linia i si coloana j reprezinta altitudinea zonei respective. Lungimea laturii unui patrat din matrice este 1. Toate cele K statii radio sunt amplasate in zone distincte de pe harta si la inaltimea corespunzatoare zonei unde sunt amplasate. In plus, ele sunt pozitionate exact in centrul zonei (in centrul patratelului respectiv din matrice). Antena radio poate fi amplasata in centrul oricarei zone care in care nu se afla o statie radio, la aceeasi altitudine cu cea a zonei sau la o altitudine mai mare (dar care sa fie neaparat un numar intreg).

Determinati cate posibilitati de amplasare a antenei radio exista. Daca antena poate fi amplasata in centrul zonei de pe linia i si coloana j la altitudinile h1 si h2 (cu h1 <> h2), acestea sunt considerate doua posibilitati diferite.

Date de intrare

Prima linie a fisierului de intrare radio.in contine 3 numere intregi, separate prin cate un spatiu: M, N si K. M si N reprezinta numarul de linii si de coloane ale hartii, iar K reprezinta numarul de statii radio. Urmatoarele M linii contin cate N numere intregi, reprezentand altitudinile zonelor respective de pe harta. Dupa aceasta, urmeaza K linii, fiecare continand cate 3 numere, separate prin cate un spatiu: i, j si R. i si j reprezinta linia si coloana zonei in care este amplasata o statie radio, iar R reprezinta raza de transmisie a statiei respective. i si j sunt numere intregi, iar R este un numar real.

Date de iesire

In fisierul de iesire radio.out veti afisa numarul total de posibilitati de a amplasa antena radio pe harta.

Restrictii

• 1 ≤ M, N ≤ 50
• 1 ≤ K ≤ min{M*N-1, 1000}
• 0 ≤ inaltimea oricarei zone ≤ 32 000
• Nu vor exista 2 statii radio amplasate in aceeasi zona de pe harta.
• La calculul distantelor, aveti grija ca sunt distante intr-un spatiu 3D.

Exemplu

Explicatie

Antena radio poate fi amplasata in zona de pe linia 3 si coloana 2, la aceeasi inaltime cu cea a zonei sau la o inaltime cu 1 mai mare. De asemenea, antena radio poate fi amplasata in zona de pe linia 3 si coloana 3, la aceeasi inaltime cu cea a zonei sau la o inaltime cu 1 mai mare.

Cum se trimit solutii?