2020 NAC Practice Contest 05

#### Start

2020-02-15 18:00 UTC

## 2020 NAC Practice Contest 05

#### End

2020-02-15 23:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -51 days 14:30:00

5:00:00

0:00:00

# Problem GApple Market

You are managing a market with some stores. The stores are arranged in an $n \times m$ grid. Each store sells apples. Apples cost exactly $1$ Malaysian Ringgit per apple at every store.

There will be several customers who walk through this market. Each customer will only visit stores within a subrectangle of the market, and each customer has a fixed amount of money to spend. Also, each store has a limited inventory of apples, which will not be replenished between customers; the number available differs from store to store. Assuming you can control how many apples each store sells to each customer, what is the most money you can make?

## Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will contain three space-separated integers $n$, $m$, and $k$, where the market has $n$ rows and $m$ columns ($1 \le n,m \le 50$), and there will be $k$ ($1 \le k \le 10^5$) customers.

Each of the next $n$ lines will have $m$ integers $a$ ($0 \le a \le 10^9$). This is a matrix in row major order, indicating the number of apples in the inventory of each store. $a[r,c]$ is the number of apples in the store in the $r^\mathrm {th}$ row, $c^\mathrm {th}$ column. The rows range from $1$ to $n$ and the columns from $1$ to $m$. The top left corner is $a[1,1]$, and the bottom right corner is $a[n,m]$.

Each of the next $k$ lines will describe a customer, with five integers: $t$, $b$ ($1 \le t \le b \le n$), $l$, $r$ ($1 \le l \le r \le m$), and $x$ ($0 \le x \le 10^9$). The customer will only shop in the subrectangle from $(t,l)$ to $(b,r)$ inclusive ($t$=top, $b$=bottom, $l$=left, $r$=right). The customer has exactly $x$ Malaysian Ringgits to spend.

## Output

Output a single integer, representing the maximum amount of money to be made by controlling how many items each store sells to each customer.

Sample Input 1 Sample Output 1
2 3 2
1 2 3
4 5 6
1 2 2 3 20
2 2 1 3 15

20