#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;pair<int,int> bars[100000];int x[1000], y[1000];int main(){int n, m, h, k, a, b, i;for(;scanf("%d%d%d%d", &n, &m, &h, &k), n;){for( i = 0; i < n; scanf("%d", y + i++ ) )x[i] = i;for( i = m; i--; bars[i] = make_pair( b, a ) )scanf("%d%d", &a, &b );sort( bars, bars + m );for( i = m ; i--; )swap( x[ bars[i].second - 1], x[ bars[i].second ] );for( i = 0; i < n; i++ ){a = y[ x[i] ];y[ x[i] ] = i;x[i] = a;}b = 0;for( i = m; i--; ){a = bars[i].second;if( ( y[a-1] < k ) != ( y[a] < k ) ){b = max( b,y[a] < k ?x[y[a]] - x[y[a-1]] :x[y[a-1]] - x[y[a]] );}swap( y[a-1], y[a] );}a = 0;for(; k--; ) a += x[k];printf("%d\n", a - b );}}