#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 35, INF = 1e18;
int f[1035][maxn][maxn][2], las[maxn][maxn][2], n, m, A, B;
vector<int> in[maxn], out[maxn];
struct ASK {
	int x, y;
}Q[maxn];
void gett(int S) {
	for(int u = 1;u <= n;u++) for(int v = 1;v <= n;v++) f[S][u][v][0] = f[S][u][v][1] = -INF;
	for(int i = 1;i <= m;i++) {
		if(!(S >> (i - 1) & 1)) continue;
		for(int v = 1;v <= n;v++) {
			for(int u : in[Q[i].x]) {
				if(f[S ^ (1 << i - 1)][Q[i].x][v][1] != -INF) f[S][u][v][0] = max(f[S][u][v][0], Q[i].y - f[S ^ (1 << i - 1)][Q[i].x][v][1]);
				if(f[S ^ (1 << i - 1)][u][Q[i].x][0] != -INF) f[S][v][u][1] = max(f[S][v][u][1], Q[i].y - f[S ^ (1 << i - 1)][u][Q[i].x][0]);
			}
		} 
	}
	while(1) {
		for(int u = 1;u <= n;u++) for(int v = 1;v <= n;v++) las[u][v][0] = f[S][u][v][0], las[u][v][1] = f[S][u][v][1];
		for(int u = 1;u <= n;u++) {
			for(int v = 1;v <= n;v++) {
				for(int x : out[u]) if(f[S][x][v][1] != -INF) f[S][u][v][0] = max(f[S][u][v][0], -f[S][x][v][1]);
				for(int x : out[v]) if(f[S][u][x][0] != -INF) f[S][u][v][1] = max(f[S][u][v][1], -f[S][u][x][0]);
			}
		}
		int flag = 0;
		for(int u = 1;u <= n;u++) for(int v = 1;v <= n;v++) for(int op = 0;op <= 1;op ++) if(las[u][v][op] != f[S][u][v][op]) flag = 1;
		if(!flag) break;
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> A >> B;
	for(int i = 1, u, v;i <= m;i++) {
		cin >> u >> v;
		out[u].push_back(v), in[v].push_back(u);
	}
	for(int i = 1;i <= m;i++) cin >> Q[i].x >> Q[i].y;
	for(int i = 1;i < (1 << m);i++) gett(i);
	cout << f[(1 << m) - 1][A][B][0];
}