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

#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 155
#define C 30010
#define M 150010
#define INF 0x3f3f3f3f
using namespace std;

int i,j,x,y,n,m,w,t,Ans=INF,cnt,lsum=1,L=1,al,Found,flow,low,high,mid;
int a[N][N],f[N][N];
int head[C],H[C],cur[C],mingap[C],gap[C],gaps[C];

struct Flow{
	int t,re,next,fl;
}e[M];

struct Line{
	int t,next;
}E[M];

inline int Min(int x,int y){return (x<y)?x:y;}

inline void Add(int s,int t,int fl){
	e[lsum].t=t;	e[lsum].fl=fl;	e[lsum].next=head[s];	
	e[lsum].re=lsum+1;	head[s]=lsum++;
	e[lsum].t=s;	e[lsum].next=head[t];
	e[lsum].re=lsum-1;	head[t]=lsum++;
}

inline void AE(int s,int t){
	E[L].t=t;	E[L].next=H[s];	H[s]=L++;
}

inline void Sap(int x){
	int i=0,F=al;
	if (x==cnt){Found=1;	flow+=al;	return;}
	for (i=cur[x];i;i=e[i].next)
	if (e[i].fl){
		if (gap[x]==gap[e[i].t]+1){
			al=Min(al,e[i].fl);	Sap(e[i].t);
			if (gap[1]>=cnt)	return;
			if (Found){cur[x]=i;	break;}
			al=F;
		}
		mingap[x]=(mingap[x]>gap[e[i].t])?gap[e[i].t]:mingap[x];
	}
	if (!Found){
		gaps[gap[x]]--;	(!gaps[gap[x]])?gap[1]=cnt:0;
		gaps[gap[x]=mingap[x]+1]++;	cur[x]=head[x];	mingap[x]=cnt-1;
	}	else e[i].fl-=al,e[e[i].re].fl+=al;
}

inline void Ready(){
	int i=0,j=0;
	cnt=1;
	for (i=1;i<=n;i++)
		for (j=1;j<=t;j++)
			f[i][j]=++cnt;
	cnt++;
}

inline void MakeMap(int c){
	int i=0,j=0,g=0;
	memset(head,0,sizeof(head));	memset(e,0,sizeof(e));
	memset(gap,0,sizeof(gap));	memset(gaps,0,sizeof(gaps));
	lsum=1;
	for (i=1;i<=n;i++){
		for (j=1;j<t;j++)
			Add(f[i][j],f[i][j+1],a[i][j]);
		Add(1,f[i][1],INF);	Add(f[i][t],cnt,a[i][t]);
	}
	for (i=1;i<=n;i++)
		for (j=H[i];j;j=E[j].next)
			for (g=c+1;g<=t;g++)
				Add(f[i][g],f[E[j].t][g-c],INF);
}

inline bool Check(int c){
	int i=0,t=0;
	MakeMap(c);
	for (i=1;i<=cnt;i++)	cur[i]=head[i],mingap[i]=cnt-1;
	gaps[1]=cnt;	flow=0;
	while (gap[1]<cnt){
		Found=0;	al=INF;	Sap(1);
	}
	return (flow<=w)?1:0;
}

int main(){
	freopen("cdcq_c.in","r",stdin);
	freopen("cdcq_c.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&w,&t);
	for (i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		AE(x,y);	AE(y,x);
	}
	for (i=1;i<=n;i++)
		for (j=1;j<=t;j++)
			scanf("%d",&a[i][j]);
	Ans=-1;	low=0;	high=t;
	Ready();
	while (low<=high){
		mid=(low+high)>>1;
		if (Check(mid))	Ans=mid,high=mid-1;
		else low=mid+1;
	}
	printf("%d\n",Ans);
	return 0;
}