记录编号	251833	评测结果	AAAAAAAEEE
题目名称	wifi	最终得分	70
用户昵称	asddddd	是否通过	未通过
代码语言	C++	运行时间	2.164 s
提交时间	2016-04-18 17:59:40	内存使用	0.71 MiB

//
//  main.cpp
//  wifi
//
//  Created by Qing Liu on 16/4/18.
//  Copyright © 2016年 Qing Liu. All rights reserved.
//

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#define inf 999999999
#define maxn 20740
using namespace std;
struct edge{
    int to,cap,rev;
};
vector<edge>G[maxn];
void addedge(int from,int to,int cap){
    //cout<<from<<" "<<to<<" "<<cap<<endl;
    G[from].push_back((edge){to,cap,(int)G[to].size()});
    G[to].push_back((edge){from,0,(int)G[from].size()-1});
}
int level[maxn],ltr[maxn];
void BFS(int s){
    bool inq[maxn];
    memset(inq,0,sizeof(inq));
    memset(level,-1,sizeof(level));
    memset(ltr, 0, sizeof(ltr));
    level[s]=0;
    queue<int>que;
    que.push(s);
    while(!que.empty()){
        int k=que.front();
        que.pop();
        for(int i=0;i<G[k].size();i++){
            edge &e=G[k][i];
            if(level[e.to]==-1&&e.cap>0){
                level[e.to]=level[k]+1;
                que.push(e.to);
            }
        }
    }
}
int DFS(int s,int t,int f){
    if(s==t)
        return f;
    for(int &i=ltr[s];i<G[s].size();i++){
        edge &e=G[s][i];
        if(e.cap>0&&level[e.to]>level[s]){
            int d=DFS(e.to,t,min(e.cap,f));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s,int t){
    int ans=0;
    BFS(s);
    while(level[t]!=-1){
        int f=DFS(s, t, inf);
        while(f>0){
            ans+=f;
            f=DFS(s, t, inf);
        }
        BFS(s);
    }
    return ans;
}
int n,m,a,b;
void init(){
    cin>>n>>m>>a>>b;
    for(int i=0;i<n;i++){
        for (int j=1; j<=m; j++) {
            int temp;
            cin>>temp;
            addedge(i*m+j, m*n+j+i*m, temp);
        }
    }
    for (int i=0; i<a; i++) {
        int x1,x2,y1,y2,z;
        cin>>x1>>y1>>x2>>y2>>z;
        addedge(0, i+2+m*2*n, z);
        for (int k=x1-1; k<x2; k++) {
            for(int j=y1;j<=y2;j++){
                addedge(i+2+m*n*2,k*m+j, inf);
            }
        }
    }
    for (int i=0;i<b;i++){
        int x1,x2,y1,y2,z;
        cin>>x1>>y1>>x2>>y2>>z;
        addedge(a+i+2+m*n*2, 2*m*n+1, z);
        for (int k=x1-1; k<x2; k++) {
            for(int j=y1;j<=y2;j++){
                addedge(m*n+k*m+j, a+i+2+m*n*2, inf);
            }
        }
    }
    cout<<max_flow(0, 2*m*n+1);
}
int main() {
    ios::sync_with_stdio(0);
    freopen("wifi.in", "r", stdin);
    freopen("wifi.out", "w", stdout);
    init();
    return 0;
}