#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
struct hori { int height, direction; };
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, h, k;
    while(cin >> n >> m >> h >> k and n and m and h and k) {
        vector<int> score(n);
        for(int i = 0; i < n; i++) {
            cin >> score[i];
        }
        vector<pair<int, int>> edges(m);
        vector<vector<hori>> horis(n);
        vector<map<int, int>> index(n);
        for(int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            a--;
            edges[i] = {a, b};
            horis[a].push_back({b, 1});
            horis[a + 1].push_back({b, -1});
        }
        for(int i = 0; i < n; i++) {
            sort(horis[i].begin(), horis[i].end(), [](auto& h1, auto& h2) {
                return h1.height < h2.height;
            });
            for(int j = 0; j < horis[i].size(); j++) {
                index[i][horis[i][j].height] = j;
            }
        }
        vector<int> nsegs(n);
        for(int i = 0; i < n; i++) {
            nsegs[i] = horis[i].size() + 1;
        }
        partial_sum(nsegs.begin(), nsegs.end(), nsegs.begin());
        auto node = [&](int i, int j) { return (i ? nsegs[i - 1] : 0) + j; };
        vector<int> next(nsegs.back());
        vector<int> height(nsegs.back());
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < horis[i].size(); j++) {
                next[node(i, j)] = node(i + horis[i][j].direction, index[i + horis[i][j].direction][horis[i][j].height] + 1);
                height[node(i, j)] = horis[i][j].height;
            }
            height[node(i, horis[i].size())] = h;
        }
        vector<int> has_path(nsegs.back());
        for(int i = 0; i < k; i++) {
            has_path[node(i, 0)] = 1;
        }
        vector<int> U(nsegs.back());
        iota(U.begin(), U.end(), 0);
        sort(U.begin(), U.end(), [&](int u, int v) { return height[u] < height[v]; });
        for(int u : U) {
            if(next[u]) {
                has_path[next[u]] = has_path[u];
            }
        }
        vector<int> ending_score(nsegs.back());
        int ans = 0;
        for(int i = 0; i < n; i++) {
            ans += has_path[node(i, horis[i].size())] * (ending_score[node(i, horis[i].size())] = score[i]);
        }
        sort(U.begin(), U.end(), [&](int u, int v) { return height[u] > height[v]; });
        for(int u : U) {
            if(next[u]) {
                ending_score[u] += ending_score[next[u]];
            }
        }
        int orig_score = ans;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < horis[i].size(); j++) {
                int new_score = orig_score;
                new_score -= has_path[node(i, j)] * ending_score[next[node(i, j)]];
                new_score -= has_path[next[node(i, j)] - 1] * ending_score[node(i, j) + 1];
                new_score += has_path[node(i, j)] * ending_score[node(i, j) + 1];
                new_score += has_path[next[node(i, j)] - 1] * ending_score[next[node(i, j)]];
                ans = min(ans, new_score);
            }
        }
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 18916