COCI '18 Contest 3 #4 NLO

View as PDF

Submit solution

Points: 15
Time limit: 1.4s
Memory limit: 64M

Problem type

The locals of the village Žabnik have been struggling for many years with unidentified flying objects (UFOs) that create circles in grain fields. The damage is particularly noticeable during summer hay mowing.

Let us imagine a rectangular grain field of N rows and M columns - the upper left field is designated by coordinates (1, 1), while the lower right field is designated by coordinates (N, M). In each field there is a certain amount of grass. Initially, amount of grass in all the fields is equal to 1. In K days UFOs of circular shape land on the field and make circles in it. On the i^\text{th} morning, the UFO of radius R_i with the center in the field designated by the coordinates (X_i, Y_i) lands on the field and "mows" all the grass growing on covered fields. In other words, the amount of grass in the field designated by coordinates (x, y) is reduced to 0 if it holds (X_i-x)^2 + (Y_i-y)^2 \le R_i^2. Each new day, with the increase of the grass, the amount of grass in all the fields increases by 1.

On K^\text{th} day in the evening, the locals will mow all the grass of the grain field that will be stored for feeding cattle. How much is the total amount of grass they will store?

Input

The first line contains positive integers N and M (1 \le N, M \le 100\,000), dimensions of the grain field.

The second line contains positive integer K (1 \le K \le 100), the number of the days in which unidentified flying objects land to the grain field before mowing.

In the i^\text{th} of the following K lines there are three positive integers X_i (1 < X_i < N), Y_i (1 < Y_i < M), and R_i (1 \le R_i \le \min(X_i-1, Y_i-1, N-X_i, M-Y_i)) which represent the central field on which the i^\text{th} UFO lands and the radius the i^\text{th} UFO.

Output

Print the total amount of grass that the locals will store after mowing.

Sample Input 1

6 6
3
4 4 2
3 3 2
2 4 1

Sample Output 1

68

Explanation of Sample Output 1

The following matrix shows amount of grass in the grain field at the end of the first day:

The following matrix shows amount of grass in the grain field at the end of the second day:

The following matrix shows amount of grass in the grain field at the end of the third day:

The total amount of grass in the grain field at the end of the third day is equal to 68.

Sample Input 2

100 100
2
50 50 49
30 30 29

Sample Output 2

9534

Sample Input 3

33333 44444
1
11111 22222 9999

Sample Output 3

1167355751

Comments

There are no comments at the moment.