#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 155
#define M 3500
#define INF 0x3f3f3f3f
using namespace std;
 
int i,n,m,w,Ans=INF,ans,cnt,lsum=1,t,x,y,j;
int a[N][N];
int f[N],c[N],head[N];
 
struct Line{
	int t,next;
}e[M];
 
inline int Abs(int x){return (x<0)?-x:x;}
inline int Min(int x,int y){return (x<y)?x:y;}
inline int Max(int x,int y){return (x>y)?x:y;}
 
inline void Add(int s,int t){
	e[lsum].t=t;	e[lsum].next=head[s];	head[s]=lsum++;
}
 
inline void Work(){
	int i=0,j=0;
	for (i=1;i<=n;i++)	f[i]=i;
	while (1){
		for (i=1;i<=n;i++)	c[i]=a[i][f[i]];
		cnt=0;	ans=0;
		for (i=1;i<=n;i++)	cnt+=c[i];
		if (cnt>w)	goto Flag;
		for (i=1;i<=n;i++)
			for (j=head[i];j;j=e[j].next)
				ans=Max(ans,Abs(f[i]-f[e[i].t]));
		Ans=Min(Ans,ans);
		Flag:
		if (!next_permutation(f+1,f+1+n)) break;
	}
	if (Ans==INF)	printf("-1\n");	else printf("%d\n",Ans);
}
 
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);
		Add(x,y);
	}
	for (i=1;i<=n;i++)
		for (j=1;j<=t;j++)
			scanf("%d",&a[i][j]);
	if (n<=40)	Work();	else printf("-1\n");
	return 0;
}