#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using pi = pair <int , int> ; 

void cmn(int &x, int y) {
    if(x > y) x = y; 
}
void cmx(int &x, int y) {
    if(x < y) x = y; 
}

cs int oo = 1e9 + 7; 

using ll = long long ;
cs int mod = 998244353; 

cs int N = 32, M = 1024;
int n, m, A, B;
vector <int> e[N];
int k; 
int w[N];
int id[N];
vector <int> f[M];

int index(int i, int j, int o){
    return o * n * n + i * n + j; 
}
int ex[N * N * 2];
int d[N * N * 2];
void work(int l, int r, cs vector <int> &c, vector <int> s, vector <int> &f, cs vector <int> &b) {
    if(l == r) {
        for(int x : s) f[x] = c[l];
        return;
    }
    int mid = (l + r) >> 1;
    static int in[N * N * 2], tim;
    ++ tim;   
    static vector <int> ee[N * N * 2];
    for(int x : s) in[x] = tim, ex[x] = 0, d[x] = 0, ee[x].clear();
    for(int x : s) {
        if(x < n * n) {
            if(b[x] >= mid)    
                ex[x] = 1; 
            else 
                ex[x] = 0; 
        }
        else {
            if(b[x] < mid) 
                ex[x] = -1; 
            else 
                ex[x] = 0;
        }
        for(int v : e[x]) 
            if(in[v] == tim) ee[x].pb(v), ++ d[v];
    }
    queue <int> q; 
    for(int x : s) 
    if(ex[x] != 0) q.push(x);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int v : ee[x]) {
            -- d[v];
            if(x < n * n) {
                
            }
        }
    }
    
}
int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
    
    cin >> n >> m >> A >> B; 
    for(int i = 0, u, v; i < m; i++) {
        scanf("%d%d", &u, &v);
        -- u, -- v; 
        e[u].pb(v);
    }
    for(int i = 0; i < n; i++) 
        id[i] = -1; 
    cin >> k; 
    for(int i = 0, x, y; i < k; i++) {
        scanf("%d%d", &x, &y);
        -- x; 
        id[x] = i; 
        w[x] = y; 
    }
    for(int S = 1; S < (1 << k); S ++) {
        f[S].resize(n * n * 2);
        vector <int> b(n * n * 2);
        for(int i = 0; i < n * n; i++)
            b[i] = - oo, b[i + n * n] = oo;
        for(int i = 0; i < n; i++) 
        for(int j = 0; j < n; j++) {
            int x = index(i, j, 0);
            for(int v : e[i])
                if(id[v] >= 0)  
                    cmx(b[x], w[v] + f[S ^ (1 << id[v])][index(v, j, 1)]);
            x = index(i, j, 1);
            for(int v : e[j])
                if(id[v] >= 0)
                    cmn(b[x], w[v] + f[S ^ (1 << id[v])][index(i, v, 0)]);
        }
        vector <int> c;
        for(int i = 0; i < n * n * 2; i++)
            if(b[i] < oo || b[i] > - oo) c.pb(b[i]);
        sort(c.begin(), c.end()); 
        vector <int> s(n * n * 2);
        for(int i = 0; i < n * n * 2; i++) s[i] = i;
        work(0, c.size() - 1, c, s, f[S], b);
    }
    return 0; 
}