题目描述

现在有一堆手机放在坐标网格里面（坐标从 $1$ 开始），坐标 $(i,j)$ 的格子有 $s_{i,j}$ 个手机。

玩手机当然需要有信号，不过这里的手机与基站与我们不太一样。基站分为两种：发送站和接收站（以下简称为 A 站和 B 站）。每个手机必须同时与一个 A 站和一个 B 站通信才能工作。

每个基站有一个正方形的覆盖范围（平行于网格）。覆盖范围可以用左下角和右上角的坐标表示（范围包括边角）。显然，手机只有在某个基站的范围内才能与这个基站通信。除此之外，每个基站还有最大接入的手机数量限制。

求最大同时工作的手机数量。

输入格式

第一行四个整数 $r,c,a,b$，表示坐标网格的规模是 $r\times c$，共有 $a$ 个 A 站和 $b$ 个 B 站。
接下来是一个 $r\times c$ 的矩阵，第 $i$ 行第 $j$ 列的数为 $s_{i,j}$。
接下来 $a$ 行，每行 $5$ 个数 $w,x1,y1,x2,y2$，表示第 $i$ 个 A 站最大接入 $w$ 个手机，覆盖范围为 $(x1,y1)-(x2,y2)$。
接下来 $b$ 行，每行 $5$ 个数 $w,x1,y1,x2,y2$，含义同上。

输出格式

一个整数，即最大同时工作的手机数量。

3 3 1 2
1 1 1
1 1 1
1 1 1
100 1 1 3 3
4 1 1 2 2
4 2 2 3 3

7

数据规模与约定

对于 $100\%$ 的数据满足 $1\le r$，$c\le 60$，$0\le a$，$b\le 10^4$，$0\le s,w\le 10^4$，$1\le x1\le x2\le r$，$1\le y1\le y2\le c$。

题目来源

Streaming #2 by saffah