rt，$\color{red}\text{WA}$ 85pts，record

#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define il inline
#define ll long long
#define lll __int128
#define ull unsigned long long
#define ld long double
#define db double
#define gc getchar();
#define pc(x) putchar(x)
#define O(x) cout<<x<<'\n';
#define adde(x,y) emplace_back(make_pair(x,y))
#define ep emplace
#define eb emplace_back
#define mp make_pair

#define pbset(typ) tree< typ ,null_type,std::less< typ >, __gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>
#define pbmap(typ1,typ2) tree< typ1 , typ2 ,std::less< typ1 >, __gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>

namespace constant_warrior{
	template<typename T> inline void fr(T& num){
		num=0;short sign=1;char ch=std::getchar();
		while(ch<'0'||ch>'9'){
			if(ch=='-')sign=-1;
			ch=std::getchar();
		}
		while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
		num=num*sign;
	}
	template<typename T>inline void fw(T x){
		if(x<0)std::putchar('-'),x=-x;
		if(x>9)fw(x/10);
		std::putchar(x%10+'0');
	}
	template<typename T>inline const T& maxf(const T& a,const T& b){
		if(a>b)return a;
		return b;
	}
	template<typename T>inline const T& minf(const T& a,const T& b){
		if(a>b)return b;
		return a;
	}
	template<typename T>inline void swapf(T& a,T& b){
		a^=b^=a^=b;
	}
	template<typename T, typename... Args> inline void fr(T &x, Args&... args) {
		fr(x);
		fr(args...);
	}
}
using namespace constant_warrior;
const int N=1<<20,M=1<<22,K=1024,inf=0x3f3f3f3f;
int n,m,k,d,a[1<<8][1<<8],b[1<<8][1<<8];
int s,t,head[N],cnt=1,fres,wres;
int dis[N],flow[N],pre[N],cur[N];
bitset<N> vis;
struct edge{
	int to,w,c,nxt;
}e[M];
inline void add(int x,int y,int w,int c){
	
	e[++cnt]=(edge){y,w, c,head[x]},head[x]=cnt;
	e[++cnt]=(edge){x,0,-c,head[y]},head[y]=cnt;
}
inline bool spfa(int s,int t){
	for(int i=1;i<=t;i++)dis[i]=inf,cur[i]=head[i];
	queue<int> q;
	q.emplace(s);
	dis[s]=0,vis[s]=1;
	while(q.size()){
		int x=q.front();
		q.pop(),vis[x]=0;
		for(int i=head[x];i;i=e[i].nxt){
			int y=e[i].to;
			if(e[i].w&&dis[y]>dis[x]+e[i].c){
				dis[y]=dis[x]+e[i].c;
				if(!vis[y])q.emplace(y),vis[y]=1;
			}
		}
	}
	return dis[t]!=inf;
}
inline int dfs(int x,int t,int flow){
	if(x==t)return flow;
	vis[x]=1;
	int res=0;
	for(int &i=cur[x];i&&res<flow;i=e[i].nxt){
		int y=e[i].to;
		if(!vis[y]&&e[i].w&&dis[y]==dis[x]+e[i].c){
			int z=dfs(y,t,min(e[i].w,flow-res));
			if(z)wres+=z*e[i].c,e[i].w-=z,e[i^1].w+=z,res+=z;
		}
	}
	return vis[x]=0,res;
}
inline pair<int,int> mcmf(){
	fres=0;
	while(spfa(s,t)){
		cerr<<"DT "<<dis[t]<<'\n';
		int x;
		while((x=dfs(s,t,inf))){
			fres+=x;
		}
	}
	return {fres,wres};
}
inline int cal(int x,int y){
	// x time ,y airport
	return (x-1)*n+y;
}
vector<int> st[N],ed[N],v[N];
void solve(){
	fr(n,m,k,d);
	s=n*d+1,t=s+1;
	add(s,cal(1,1),k,0);
	add(cal(d,1),t,k,0);
	for(int i=1;i<d;i++){
		for(int j=1;j<=1;j++){
			add(cal(i,j),cal(i+1,j),inf,0);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			fr(a[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			fr(b[i][j]);
		}
	}
	for(int i=1;i<=m;i++){
		int x,y,u,v,w;
		fr(x,y,u,v,w);
		x++,y++,u++,v++;
		st[x].emplace_back(u);
		ed[y].emplace_back(v);
		add(cal(u,x),cal(v,y),1,-w);
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			for(auto k:st[j]){
				if(k-a[i][j]+1<=0)continue;
				add(cal(k-a[i][j]+1,i),cal(k,j),inf,b[i][j]);
				v[i].emplace_back(k-a[i][j]+1);
			}
			for(auto k:ed[i]){
				if(k>d-a[i][j]+1)continue;
				add(cal(k,i),cal(k+a[i][j]-1,j),inf,b[i][j]);
				v[j].emplace_back(k+a[i][j]-1);
			}
		}
	}
	for(int i=2;i<=n;i++){
		for(auto j:st[i])v[i].emplace_back(j);
		for(auto j:ed[i])v[i].emplace_back(j);
		sort(v[i].begin(),v[i].end());
		v[i].erase(unique(v[i].begin(),v[i].end()),v[i].end());
		
		for(int j=1;j<v[i].size();j++){
			add(cal(v[i][j-1],i),cal(v[i][j],i),inf,0);
		}
	}
	mcmf();
	fw(-wres);
}
int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	int T=1;//cin>>T;
	while(T-->0)solve();
}
/*
暴力出奇迹，卡常能AC。
Violent makes miracle,pursuing better constant can AC.
多测不清空，OI见祖宗。
multitesting without clearing,oier meets the LCA.
十年OI一场空，不开LL见祖宗。
Ten years of OI just AFO,no #define int long long sees the LCA.
似是神犇成才处，实为蒟蒻黄泉路。
It is likely to be the Au medal for the big old,but in fact it is the Si medal for me.
黄题有恨无正解，码力不若小学生。
A yellow problem I can't AC,codeforces is not as NB as XXS.
今生无奈入OI，来世不做信竞人。
This life I am a Siliy Being in oi,next life I won't f**k the sh*t of infomatics.
*/