#P3577. 玩手机

    ID: 2776 传统题 1000ms 128MiB 尝试: 236 已通过: 66 难度: 8 上传者: 标签>难度分类提高+/省选-图论Dinic拆点限制点容量辅助点压缩边排序与序列处理倍增当前弧优化CF2400

玩手机

玩手机

题目描述

一个 r×cr\times c 的网格上,第 (i,j)(i,j) 个格子里有 si,js_{i,j} 部手机。每部工作的手机必须接入一个发送站(A 站)和一个接收站(B 站)。

每个基站的覆盖区域是一个边与网格平行的正方形,由左下角和右上角的坐标给出,包含边界上的所有格子。手机只能接入覆盖其所在格子的基站。每个基站还有接入手机数的上限。

求最多有多少部手机能同时工作。

输入格式

第一行四个整数 r,c,a,br,c,a,b,依次表示网格行数、列数、A 站数、B 站数。

接下来 rr 行,每行 cc 个整数,给出 si,js_{i,j}。接下来 aa 行给出 A 站,最后 bb 行给出 B 站。每个基站用五个整数 w,x1,y1,x2,y2w,x_1,y_1,x_2,y_2 描述,其中 ww 是接入上限,(x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2) 分别是覆盖区域左下角和右上角。

输出格式

输出一行一个整数,表示最多有多少部手机能同时工作。

样例

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≤601\le r,c\le60,0≤a,b≤1040\le a,b\le10^4,0≤si,j,w≤1040\le s_{i,j},w\le10^4。

1≤x1≤x2≤r1\le x_1\le x_2\le r,1≤y1≤y2≤c1\le y_1\le y_2\le c,且 x2−x1=y2−y1x_2-x_1=y_2-y_1。