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.

#### Sample Input

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

#### Sample Output

11

Author:

**WU, Yingxin**
Submit
Status