记录编号	393762	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	源符「厌川的翡翠」	最终得分	100
用户昵称	cdcq	是否通过	通过
代码语言	C++	运行时间	3.055 s
提交时间	2017-04-12 07:48:05	内存使用	28.44 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int oo=168430090;
int rd(){int z=0,mk=1;  char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')mk=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
	return z*mk;
}
struct ddd{int nxt,y,v,rvs;}e[510000];  int lk[310000],ltp=0;
inline void ist(int x,int y,int z){
	e[++ltp].nxt=lk[x],lk[x]=ltp,e[ltp].y=y,e[ltp].v=z,e[ltp].rvs=ltp+1;
	e[++ltp].nxt=lk[y],lk[y]=ltp,e[ltp].y=x,e[ltp].v=0,e[ltp].rvs=ltp-1;
}
ddd E[21000];  int LK[110000],LTP=0;
inline void IST(int x,int y){  E[++LTP].nxt=LK[x],LK[x]=LTP,E[LTP].y=y;}
int n,m,w,v,a[2100][2100];
int s,t;
int lvl[210000];
int q[210000],hd=0;
bool gtlvl(){
	memset(lvl,0,sizeof(lvl));
	q[hd=1]=s,lvl[s]=1;
	for(int k=1;k<=hd;++k)for(int i=lk[q[k]];i;i=e[i].nxt)
		if(e[i].v && !lvl[e[i].y])  lvl[e[i].y]=lvl[q[k]]+1,q[++hd]=e[i].y;
	return lvl[t];
}
int mxflw(int x,int y){
	//cout<<x<<" "<<y<<endl;
	if(x==t)  return y;
	int bwl=0,flw;
	for(int i=lk[x];i && bwl<y;i=e[i].nxt)if(e[i].v && lvl[e[i].y]==lvl[x]+1)
		if((flw=mxflw(e[i].y,min(y-bwl,e[i].v)))){
			bwl+=flw;
			e[i].v-=flw,e[e[i].rvs].v+=flw;
		}
	if(!bwl)  lvl[x]=0;
	return bwl;
}
int dnc(){
	int bwl=0,flw;
	while(gtlvl())while((flw=mxflw(s,oo)))  bwl+=flw;
	return bwl;
}
int gtid(int x,int y){  return (x-1)*(v+1)+y+1;}
void clr(){  memset(lk,0,sizeof(lk)),ltp=0;}
bool chck(int x){
	clr();
	for(int k=1;k<=n;++k){
		ist(s,gtid(k,0),oo),ist(gtid(k,v),t,oo);
		for(int j=1;j<=v;++j)  ist(gtid(k,j-1),gtid(k,j),a[k][j]);
		for(int j=x;j<=v;++j)
			for(int i=LK[k];i;i=E[i].nxt)
				ist(gtid(k,j),gtid(E[i].y,j-x),oo);
	}
	return dnc()<=w;
}
int bnrsch(){
	int l=0,r=v,md;
	while(l+1<r)  md=(l+r)>>1,(chck(md) ? r : l)=md;
	return chck(l) ? l : r;
}
int main(){
	freopen("cdcq_c.in","r",stdin);
	freopen("cdcq_c.out","w",stdout);
	cin>>n>>m>>w>>v;  s=0,t=(n+1)*(v+1)+1;
	int l,r;
	for(int i=1;i<=m;++i)  l=rd(),r=rd(),IST(l,r),IST(r,l);
	for(int i=1;i<=n;++i)for(int j=1;j<=v;++j)  a[i][j]=rd();
	int ans=bnrsch();
	cout<<(ans==v ? -1 : ans)<<endl;
	return 0;
}