dinic没问题，帮忙看建图谢

#include<bits/stdc++.h>
#define ll long long
#define rep(i,aaa,bbb) for(int i=(aaa);i<=(bbb);i++)
#define per(i,aaa,bbb) for(int i=(aaa);i>=(bbb);i--)
#define all(a) (a).begin(),(a).end()
#define edl cout<<endl
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define l first
#define r second
#define ptln(...) print(__VA_ARGS__,"\n")
using namespace std;

template<typename T>inline void read(T&x){cin>>x;}
template<typename T,typename...Args>inline void read(T&x,Args&...args){read(x);read(args...);}
template<typename T>inline void print(const T&x){cout<<x;}
template<typename T,typename...Args>inline void print(const T&x,Args&&...args){cout<<x<<" ";print(args...);}

constexpr int inf=0x7f7f7f7f;
constexpr int maxn=4e3+10;

struct edge{
	int v,f,c,b;
	edge(int vv,int ff,int cc,int bb):v(vv),f(ff),c(cc),b(bb){};
};

int n,m,K;
int df[210][210],dt[210][210];
int id[210][3010];
int tot;
vector<edge>G[maxn];

struct Dinic{
	int S=1,T;
	int V[maxn];
	int dis[maxn];
	int cur[maxn];
	int minCost;
	
	bool spfa(){
		memset(dis,0x7f,sizeof dis);
		memset(cur,0,sizeof cur);
		queue<int>Q;
		Q.push(S),dis[S]=0,V[S]=1;
		while(!Q.empty()){
			int x=Q.front();Q.pop(),V[x]=0;
//			ptln("Q",x);
			for(edge j:G[x]){
				if(j.f&&dis[j.v]>dis[x]+j.c){
					dis[j.v]=dis[x]+j.c;
					if(!V[j.v])Q.push(j.v),V[j.v]=1;
				}
			}
		}
//		ptln("SPFA",dis[T]);
		return dis[T]!=inf;
	}
	
	int dfs(int x,int flow){
		if(x==T)return flow;
		V[x]=1;
		int ans=0;
		for(int&i=cur[x];i<(int)G[x].size()&&flow>ans;++i){
			int v=G[x][i].v,f=G[x][i].f,c=G[x][i].c,b=G[x][i].b;
			if(!V[v]&&f&&dis[v]==dis[x]+c){
				int res=dfs(v,min(f,flow-ans));
				if(res){
//					ptln("Cost",res,c);
					minCost+=res*c;
					G[x][i].f-=res;
					G[v][b].f+=res;
					ans+=res;
				}
			}
		}
		V[x]=0;
//		ptln("maxFlow",x,ans);
		return ans;
	}
	
	int mcmf(){
		int ans=0;
		while(spfa()){
			while(int x=dfs(S,K))ans+=x;
		}
		return ans;
	}
}dinic;

void add(int a,int s,int b,int t,int f,int c){//(a,s)--f,c-->(b,t)
	if(s<0||t>dinic.T)return;
	int x=id[a][s]?id[a][s]:(id[a][s]=++tot);
	int y=id[b][t]?id[b][t]:(id[b][t]=++tot);
	G[x].eb(y,f,c, (int)G[y].size() ),G[y].eb(x,0,-c, (int)G[x].size()-1 );
}

int main(){//ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	read(n,m,K,dinic.T);
	rep(i,0,n-1)rep(j,0,n-1)read(dt[i][j]);
	rep(i,0,n-1)rep(j,0,n-1)read(df[i][j]);
	rep(i,0,dinic.T-1)add(0,i,0,i+1,K,0);
	rep(i,1,m){
		int a,b,s,t,c;read(a,b,s,t,c);
		add(0,s-dt[0][a],a,s,1,df[0][a]);
		add(a,s,b,t,1,-c);
		add(b,t,0,t+dt[b][0],K,df[b][0]);
//		ptln(0,s-dt[0][a],a,s,1,df[0][a]);
//		ptln(a,s,b,t,1,-c);
//		ptln(b,t,0,t+dt[b][0],K,df[b][0]);
	}
	rep(i,1,n-1){
		int now=-1;
		rep(j,0,dinic.T){
			if(!id[i][j])continue;
			if(now==-1){
				now=j;
				continue;
			}
			add(i,now,i,j,K,0);
			now=j;
		}
	}
	dinic.T+=1;
	dinic.mcmf();
	print(-dinic.minCost);
	return 0;
}

/*
2 1 1 10
0 5
5 0
0 5
5 0
0 1 0 5 10
*/