import std.stdio;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;

struct P {
    int a, b;
    int x, y;
    int opCmp(const ref P p) const {
        return b - p.b;
    }
}

void main() {
    int n, m, h, k;
    while (scanf("%d %d %d %d\n", &n, &m, &h, &k), n || m || h || k) {
        int[] ps;
        foreach (i; 0 .. n) {
            int p;
            scanf("%d\n", &p);
            ps ~= p;
        }
        P[] ss;
        foreach (i; 0 .. m) {
            int a, b;
            scanf("%d %d\n", &a, &b);
            a--; b--;
            ss ~= P(a, b);
        }
        ss = ss.sort.array;
        int[] xs = new int[n];
        foreach (i; 0 .. n) xs[i] = i;
        foreach (i; 0 .. m) {
            int x = ss[i].a,
                y = ss[i].a + 1;
            ss[i].x = xs[x];
            ss[i].y = xs[y];
            swap(xs[x], xs[y]);
        }
        int[] _ps = ps.dup;
        foreach (i; 0 .. n) {
            ps[xs[i]] = _ps[i];
        }
        int t = 0;
        foreach (i; 0 .. k) {
            t += ps[i];
        }
        int ans = t;
        foreach (i; 0 .. m) {
            int x = ss[i].x,
                y = ss[i].y;
            if (0 <= x && x < k) {
                if (0 <= y && y < k) continue;
                else ans = min(ans, t - ps[x] + ps[y]);
            } else if (0 <= y && y < k) {
                ans = min(ans, t - ps[y] + ps[x]);
            }
        }
        ans.writeln;
    }
}