/*
  t3
  2017.04.01
    ---wyj
*/
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n,m,w,t,f[500][500],hehe[500][500],r[500],maxx=9999999;
struct node
{
  int x,y,v,next;
}a[20200];int LINK[20200],len=0;
void insert(int xx,int yy,int vv)
{
  a[++len].next=LINK[xx];LINK[xx]=len;
  a[len].x=xx;a[len].y=yy;a[len].v=vv;
}
int abs(int a,int b)
{
  if(a>=b) return a-b;
  else     return b-a;
}
void dfs(int x,int yy,int maxa)
{
  if(yy>w)  return;
  if(maxa>maxx) return;
  if(x==n)
  {
    for(int i=1;i<=t;i++)
    {
	  int u=maxa;r[x]=i;
	  if(yy+hehe[x][i]<=w)
	  {
	    for(int j=LINK[i];j;j=a[j].next)
		   maxa=max(maxa,abs(r[x],r[a[j].y]));
		maxx=min(maxx,maxa);
	  }
	}
	return;
  }
  for(int i=1;i<=t;i++)
  {
     int u=maxa;r[x]=i;
	 for(int j=LINK[i];j;j=a[j].next)
		if(a[j].y<x) u=max(maxa,abs(r[x],r[a[j].y]));
	 dfs(x+1,yy+hehe[x][i],u);
  }
}
int main()
{
  freopen("cdcq_c.in","r",stdin);
  freopen("cdcq_c.out","w",stdout);
  scanf("%d%d%d%d",&n,&m,&w,&t);
  int c1,c2;memset(hehe,0,sizeof(hehe));
  for(int i=1;i<=m;i++)
  {
    scanf("%d%d",&c1,&c2);
	f[c1][c2]=f[c2][c1]=1;
	insert(c1,c2,1);insert(c2,c1,1);
  }
  for(int i=1;i<=n;i++)
	for(int j=1;j<=t;j++)
	  scanf("%d",&hehe[i][j]);
  if(n<=10) 
  {
	  dfs(1,0,0);
      cout<<maxx<<endl;
  }
  return 0;
}