玩手机
题目描述
一个 r×c 的网格上,第 (i,j) 个格子里有 si,j 部手机。每部工作的手机必须接入一个发送站(A 站)和一个接收站(B 站)。
每个基站的覆盖区域是一个边与网格平行的正方形,由左下角和右上角的坐标给出,包含边界上的所有格子。手机只能接入覆盖其所在格子的基站。每个基站还有接入手机数的上限。
求最多有多少部手机能同时工作。
输入格式
第一行四个整数 r,c,a,b,依次表示网格行数、列数、A 站数、B 站数。
接下来 r 行,每行 c 个整数,给出 si,j。接下来 a 行给出 A 站,最后 b 行给出 B 站。每个基站用五个整数 w,x1,y1,x2,y2 描述,其中 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≤104,0≤si,j,w≤104。
1≤x1≤x2≤r,1≤y1≤y2≤c,且 x2−x1=y2−y1。