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

市场中会有几位顾客光顾。每位顾客只会访问市场内的一个子矩形区域内的商店，且每位顾客都有固定的预算。此外，每家商店的苹果库存有限，且在顾客之间不会补充；不同商店的库存数量各不相同。假设你可以控制每家商店卖给每位顾客的苹果数量，请问你最多能赚取多少钱？

输入格式

输入包含一组测试数据。注意，你的程序可能会在不同的输入上运行多次。输入的第一行包含三个空格分隔的整数 $n$、$m$ 和 $k$，其中市场有 $n$ 行 $m$ 列 ($1 \le n, m \le 50$)，共有 $k$ 位顾客 ($1 \le k \le 10^5$)。

接下来的 $n$ 行，每行包含 $m$ 个整数 $a$ ($0 \le a \le 10^9$)。这是一个按行优先顺序排列的矩阵，表示每家商店的苹果库存数量。$a[r, c]$ 表示第 $r$ 行第 $c$ 列商店的苹果数量。行号范围为 $1..n$，列号范围为 $1..m$。左上角为 $a[1, 1]$，右下角为 $a[n, m]$。

接下来的 $k$ 行，每行描述一位顾客，包含五个整数：$t, b$ ($1 \le t \le b \le n$)，$l, r$ ($1 \le l \le r \le m$) 以及 $x$ ($0 \le x \le 10^9$)。该顾客只会在从 $(t, l)$ 到 $(b, r)$（包含边界）的子矩形区域内购物（$t=$ 上边界，$b=$ 下边界，$l=$ 左边界，$r=$ 右边界）。该顾客恰好有 $x$ 马来西亚林吉特的预算。

输出格式

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

样例

样例输入 1

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

样例输出 1

20