C++ :

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define ll long long
#define hh puts("")
#define time TTTT
using namespace std;
int n,m,k,tim,t[205][205],w[205][205],head[100005],vis[100005],dis[100005],cnt=1,cost,ans,time,st,ed;
struct node
{
    int a,b,s,t,c;
}q[1005];struct Edge{int v,nx,s,val;}e[1000005];
inline int read(){int ret=0,ff=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}return ret*ff;}inline void add(int x,int y,int val,int s){
    e[++cnt].v=y;e[cnt].val=val;e[cnt].s=s;e[cnt].nx=head[x];head[x]=cnt;
}
inline bool spfa()
{
    for(int i=0;i<=ed;i++)dis[i]=-1e9,vis[i]=0;queue<int>q;dis[st]=0;q.push(st);while(!q.empty()){int now=q.front();q.pop();vis[now]=0;for(int i=head[now];i;i=e[i].nx){int v=e[i].v;if(dis[v]<dis[now]+e[i].val&&e[i].s){dis[v]=dis[now]+e[i].val;if(!vis[v]){vis[v]=1;q.push(v);}}}}return dis[ed]!=-1e9;
}
int dfs(int now,int ma){
    if(now==ed){ans+=ma;return ma;}vis[now]=time;int used=0,t;for(int i=head[now];i;i=e[i].nx){int v=e[i].v;if((vis[v]!=time||v==ed)&&e[i].s&&dis[v]==dis[now]+e[i].val){if(t=dfs(v,min(ma-used,e[i].s))){e[i].s-=t;e[i^1].s+=t;cost+=t*e[i].val;used+=t;if(used==ma) break;}}}return used;
}
signed main(){n=read(),m=read(),k=read(),tim=read();for(int i=0;i<n;i++)for(int j=0;j<n;j++)t[i][j]=read();for(int i=0;i<n;i++)for(int j=0;j<n;j++)w[i][j]=read();st=m*2+5,ed=m*2+10;for(int i=1;i<=m;i++){q[i].a=read();q[i].b=read();q[i].s=read();q[i].t=read();q[i].c=read();}for(int i=1;i<=m;i++){add(i*2-1,i*2,q[i].c,1);add(i*2,i*2-1,-q[i].c,0);if(q[i].t+t[q[i].b][0]<=tim){add(i*2,ed,-w[q[i].b][0],1e9);add(ed,i*2,w[q[i].b][0],0);}else continue;if(t[0][q[i].a]<=q[i].s){add(st+1,i*2-1,-w[0][q[i].a],1e9);add(i*2-1,st+1,w[0][q[i].a],0);}for(int j=1;j<=m;j++){if(q[i].t+t[q[i].b][q[j].a]<=q[j].s){
                add(i*2,j*2-1,-w[q[i].b][q[j].a],1e9);
                add(j*2-1,i*2,w[q[i].b][q[j].a],0);
            }
        }
    }
    add(st,st+1,0,k);
    add(st+1,st,0,0);
    while(spfa()){
        do{
            time++;
            dfs(st,1e9);
        }while(vis[ed]==time);
    }
    printf("%d",cost);
    return 0;
}