#3577. 玩手机

内存限制:32 MiB 时间限制:12 Sec

题目描述

现在有一堆手机放在坐标网格里面(坐标从1开始),坐标(i,j)的格子有s_(i,j)个手机。
玩手机当然需要有信号,不过这里的手机与基站与我们不太一样。基站分为两种:发送站和接收站(以下简称为A站和B站)。每个手机必须同时与一个A站和一个B站通信才能工作。
每个基站有一个正方形的覆盖范围(平行于网格)。覆盖范围可以用左下角和右上角的坐标表示(范围包括边角)。显然,手机只有在某个基站的范围内才能与这个基站通信。除此之外,每个基站还有最大接入的手机数量限制。
求最大同时工作的手机数量。

输入格式

第一行四个整数R,C,a,b,表示坐标网格的规模是R×C,共有a个A站和b个B站。
接下来是一个R×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

数据规模与约定
1≤R,C≤60,0≤a,b≤10,000,0≤s,w≤10,000,1≤x1≤x2≤R,1≤y1≤y2≤C。


数据范围与提示