#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 155, MAXM = 205, MAXT = 205;

int n, m, w, t, v[MAXN][MAXT];

namespace Graph {
	int head[MAXN], nxt[MAXM<<1], to[MAXM<<1], eidx = 0;
	void init() {
		memset(head, -1, sizeof(head));
	}
	void adde( int u, int v ) {
		to[eidx] = v, nxt[eidx] = head[u], head[u] = eidx++;
		to[eidx] = u, nxt[eidx] = head[v], head[v] = eidx++;
	}
}

namespace Solve {
	void input() {
		scanf( "%d%d%d%d", &n, &m, &w, &t );
		for( int i = 0; i < m; ++i ) {
			int u, v; scanf( "%d%d", &u, &v );
			Graph::adde(u,v);
		}
		for( int i = 1; i <= n; ++i )
			for( int j = 1; j <= t; ++j )
				scanf( "%d", &v[i][j] );
	}
	bool check() {
		int sum = 0;
		for( int u = 1; u <= n; ++u )
			sum += *min_element(v[u]+1, v[u]+t+1);
		return sum <= w;
	}
}

namespace Solve1 {
	int ans = INF, f[MAXN];
	void update() {
		using namespace Graph;
		int c = 0;
		for( int u = 1; u <= n; ++u ) {
			// printf( "f[%d] = %d\n", u, f[u] );
			for( int e = head[u]; ~e; e = nxt[e] ) {
				int v = to[e];
				c = max(c, abs(f[u] - f[v]));
			}
		}
		ans = min(ans, c);
	}
	void dfs( int u, int totw ) {
		if( totw > w ) return;
		if( u == n+1 ) {
			// printf( "totw = %d, w = %d\n", totw, w );
			update();
			return;
		}
		for( int i = 1; i <= t; ++i ) {
			f[u] = i;
			dfs(u+1, totw + v[u][i]);
		}
	}
	void solve() {
		dfs(1,0);
		printf( "%d\n", ans );
	}
}

int main() {
	freopen( "cdcq_c.in", "r", stdin );
	freopen( "cdcq_c.out", "w", stdout );
	Graph::init();
	Solve::input();
	if( !Solve::check() ) puts("-1");
	else Solve1::solve();
	return 0;
}