ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

## Romanian Open Contest December 2001

Contest is over

Time limit: 1.0 second
Memory limit: 64 MB
The map of Romania is given as a M*N matrix, where the value in row i and column j represents the altitude of the corresponding zone. The side of a square in this matrix is 1. All the K radio stations are placed at distinct coordinates on the map and at the same height as the corresponding zone (plus, they are placed exactly in the center of their square). The radio receiver can be placed in the center of any square not occupied by a radio station, at the same altitude of the square or it can be placed higher with an integer number of meters. The radio receiver cannot be placed in a square occupied by a radio station.
Your task is to decide how many possibilities to place the radio receiver the government has. Note that if the radio receiver may be placed in row i and column j at altitudes h1 and h2 (h1 ≠ h2), this counts as 2 different possibilities.

### Input

The first line of input contains 3 integers: M, N (1 ≤ M, N ≤ 50) and K (1 ≤ K ≤ min(M*N-1, 1000)), representing the dimensions of the map and the number of radio stations. Next there are M lines each containing N integers, which are the altitudes of the zones on the map (no altitude will be higher than 32000 or lower than 0). After that, there will be K lines, each containing 3 numbers: i, j and R. i and j will be the location of the radio station on the map and R will be its broadcast radius (R is a real number, not larger than 100000 and not less than 0).
No two radio stations will be placed on the same square.

### Output

You should output one integer number, which is the total number of valid possibilities to place the radio receiver on the map.

inputoutput
```5 5 3
1 2 3 4 5
6 7 8 9 10
1 2 3 4 5
6 7 8 9 10
5 4 3 2 1
1 1 4.3
5 5 4.3
5 1 4.3
```
```4
```

### Notes

The radio receiver can be placed at position (3, 2), with extra height 0 and extra height 1, and at position (3, 3), with extra height 0 and extra height 1. So, there are 4 possible ways to place the receiver.
When you compute distances, be aware that they are distances in a 3D space.
Problem Author: Mugurel Ionut Andreica
Problem Source: Romanian Open Contest, December 2001
To submit the solution for this problem go to the Problem set: 1168. Radio Stations