Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3578
Matrix

Time Limit: 10 Seconds      Memory Limit: 131072 KB

A N*M coordinate plane ((0, 0)~(n, m)). Initially the value of all N*M grids are 0.
An operation T(a, b, h, x, y) is defined as follow:
1. Select the maximum value in the matrix (x, y) ~ (x+a, y+b), suppose the maximum value is max
2. Change all the value in the matrix (x, y) ~ (x+a, y+b) into max+h
After C operations, please output the maximum value in the whole N*M coordinate.

#### Input

The input consists of several cases.
For each case, the first line consists of three positive integers N , M and C (N ≤ 1000, M ≤ 1000, C ≤ 1000). In the following C lines, each line consists of 5 non-negative number, ai, bi, hi, xi, yi (0 ≤ hi ≤ 10000, 0 ≤ xi < n, 0 ≤ yi < m).

#### Output

For each case, output the maximum height.

```3 2 2
2 1 9 1 1
1 1 2 2 1
```

#### Sample Output

```11
```

Author: WU, Yingxin
Contest: ZOJ Monthly, February 2012
Submit    Status