题目描述

你正在管理一个拥有若干商店的市场。这些商店排列在一个 $n \times m$ 的网格中。每家商店都销售苹果。每家商店的苹果价格均为每颗 1 马来西亚林吉特。

会有若干顾客穿过这个市场。每位顾客只会访问市场内某个子矩形中的商店，并且每位顾客有固定金额的资金可以消费。此外，每家商店的苹果库存有限，且在不同顾客之间不会补货；每家商店的库存数量各不相同。假设你可以控制每家商店向每位顾客出售多少苹果，请问你最多能赚多少钱？

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入的第一行包含三个空格分隔的整数 $n$、$m$ 和 $k$，其中市场有 $n$ 行和 $m$ 列（$1 \leq n, m \leq 50$），并且有 $k$（$1 \leq k \leq 10^5$）位顾客。

接下来的 $n$ 行，每行包含 $m$ 个整数 $a$（$0 \leq a \leq 10^9$）。这是一个按行主序排列的矩阵，表示每家商店的苹果库存数量。$a[r, c]$ 表示位于第 $r$ 行、第 $c$ 列商店的苹果数量。行编号从 $1$ 到 $n$，列编号从 $1$ 到 $m$。左上角为 $a[1, 1]$，右下角为 $a[n, m]$。

接下来的 $k$ 行，每行描述一位顾客，包含五个整数：$t$、$b$（$1 \leq t \leq b \leq n$）、$l$、$r$（$1 \leq l \leq r \leq m$）和 $x$（$0 \leq x \leq 10^9$）。该顾客只会访问从 $(t, l)$ 到 $(b, r)$ 的子矩形（包含边界），其中 $t$ 表示上边界，$b$ 表示下边界，$l$ 表示左边界，$r$ 表示右边界。该顾客恰好有 $x$ 马来西亚林吉特可以消费。

输出格式

输出一个整数，表示通过控制每家商店向每位顾客出售的商品数量所能获得的最大金额。

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

20

提示

翻译由 DeepSeek V3.2 完成