bzoj#P3577. 玩手机

玩手机

题目描述

现在有一堆手机放在坐标网格里面(坐标从 11 开始),坐标 (i,j)(i,j) 的格子有 si,js_{i,j} 个手机。

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

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

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

输入格式

第一行四个整数 r,c,a,br,c,a,b,表示坐标网格的规模是 r×cr\times c,共有 aa 个 A 站和 bb 个 B 站。
接下来是一个 r×cr\times c 的矩阵,第 ii 行第 jj 列的数为 si,js_{i,j}
接下来 aa 行,每行 55 个数 w,x1,y1,x2,y2w,x1,y1,x2,y2,表示第 ii 个 A 站最大接入 ww 个手机,覆盖范围为 (x1,y1)(x2,y2)(x1,y1)-(x2,y2)
接下来 bb 行,每行 55 个数 w,x1,y1,x2,y2w,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%100\% 的数据满足 1r1\le rc60c\le 600a0\le ab104b\le 10^40s,w1040\le s,w\le 10^41x1x2r1\le x1\le x2\le r1y1y2c1\le y1\le y2\le c

题目来源

Streaming #2 by saffah