#include <cstdio>
#include <cstdlib>

int LIMIT,tot,n,m,t,w,ans=-1,v[1010][1010],head[1010],to[2010],next[2010];
int cho[1010];

inline void AE(int u,int v){
	++tot; to[tot]=v;
	next[tot]=head[u]; head[u]=tot;
}

inline int abs(int x){ return x<0?-x:x; }
inline int max(int a,int b){return a>b?a:b;}

void dfs(int u,int val){
	if(val>w) return;
	if(u==n+1){
		int mx=0;
		for(int i=1;i<=n;i++)
			for(int p=head[i];p;p=next[p])
				mx=max(mx,abs(cho[to[p]]-cho[i]));
		(ans>mx||ans<0)?ans=mx:false;
		return;
	}
	for(int i=1;i<=t;i++){
		cho[u]=i;
		dfs(u+1,val+v[u][i]);
	}
}

int main(){
	freopen("cdcq_c.in","r",stdin);
	freopen("cdcq_c.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&w,&t);
	for(int i=1;i<=m;i++){
		int x,y; scanf("%d%d",&x,&y);
		AE(x,y); AE(y,x);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=t;j++)
			scanf("%d",&v[i][j]);
	if(n>10){
		printf("-1");
		return 0;
	}
	dfs(1,0);
	printf("%d\n",ans);
	return 0;
}