题目描述

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?

输入格式

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 \leq n, m \leq 50$), and there will be $k$ ($1 \leq k \leq 10^5$) customers.

Each of the next $n$ lines will have $m$ integers $a$ ($0 \leq a \leq 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^{\text{th}}$ row, $c^{\text{th}}$ column. The rows range from $1..n$ and the columns from $1..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 \leq t \leq b \leq n$), $l$, $r$ ($1 \leq l \leq r \leq m$), and $x$ ($0 \leq x \leq 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 a single integer, representing the maximum amount of money to be made by controlling how many items each store sells to each customer.

2 3 2
1 2 3
4 5 6
1 2 2 3 20
2 2 1 3 15

20