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 spaceseparated 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
