Apple Market

You manage a market made up of several stores. The stores are arranged in an $n \times m$ grid, and every store sells apples. At every store, one apple costs exactly 1 Malaysian Ringgit.

Several customers walk through this market. Each customer visits only the stores inside one subrectangle of the market and has a fixed amount of money to spend. Each store has a limited inventory of apples, which differs from store to store and is not replenished between customers. If you can decide how many apples each store sells to each customer, what is the most money you can make?

The input consists of a single test case. Your program may be run several times on different inputs. The first line contains three space-separated integers $n$, $m$, and $k$: the market has $n$ rows and $m$ columns ($1 \le n, m \le 50$), and there are $k$ customers ($1 \le k \le 10^5$).

Each of the next $n$ lines contains $m$ integers $a$ ($0 \le a \le 10^9$). This matrix, in row-major order, gives the number of apples in the inventory of each store. $a[r, c]$ is the number of apples in the store in row $r$, column $c$. Rows are numbered $1$ to $n$ and columns $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 describes one 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 shops only in the subrectangle from $(t, l)$ to $(b, r)$ inclusive ($t$ is top, $b$ is bottom, $l$ is left, $r$ is right). The customer has exactly $x$ Malaysian Ringgits to spend.

Print a single integer: the maximum amount of money you can make by deciding how many apples each store sells to each customer.