Zak Galou

#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()
#define forn(l, r) for(int i = l; i < (r); ++i)
#define F first
#define S second
#define $ ios::sync_with_stdio(0);

using namespace std;

using ll = long long int;
using ii = pair<int, int>;
using vi = vector<int>;

const int INF = 0x3f3f3f3f;
const int MAXN = -1;

//MAGIA
int m;
int magic_cost[1123], magic_dmg[1123];

//DP
int dp[1123][1123];
int seen[1123][1123], TC = 0;

//GRAFO
vector<vi> graph;
vi w;

int sol (int magic, int life) {
    if (life <= 0) return 0;
    if (magic == m) return INF;
    if (seen[magic][life] == TC) return dp[magic][life];

    int next_magic = sol(magic + 1, life);
    int get_magic  = sol(magic, life - magic_dmg[magic]) + magic_cost[magic];

    seen[magic][life] = TC;

    return dp[magic][life] = min(next_magic, get_magic);
}

int dijkstra (int origin, int destiny) {

    vi dist(1001, INF);
    priority_queue<ii> pq;

    dist[origin] = w[origin];
    pq.push({dist[origin], origin});

    ii cur;
    int node, mp;
    int ts;

    while (!pq.empty()) {
        cur = pq.top();
        node = cur.S;
        mp = -cur.F;

        pq.pop();

        if (mp > dist[node]) continue;

        for (auto edge : graph[node]) {
            ts = w[edge] + dist[node];
            if (ts < dist[edge]) {
                dist[edge] = ts;
                pq.push({-ts, edge});
            }
        }
    }

    return dist[destiny];
}


int32_t main() {

    int n, g, k;
    int a, b;
    int ans;

    while (scanf("%d %d %d %d", &m, &n, &g, &k) && m) {
        ++TC;

        forn (0, m) {
            scanf("%d %d", &magic_cost[i], &magic_dmg[i]);
        }

        graph.assign(n + 1, vi());
        forn (0, g) {
            scanf("%d %d", &a, &b);
            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        w.assign(n + 1, 0);
        forn (0, k) {
            scanf("%d %d", &a, &b);
            w[a] += sol(0, b);
        }

        ans = dijkstra(1, n);

        printf("%d\n", ans < INF ? ans : -1);

    }

}