Problema

Estás jugando con J-kun usando un Amidakuji (lotería de escalera fantasma). El Amidakuji consta de $n$ barras verticales y $m$ barras horizontales. Las barras verticales están numeradas de $1$ a $n$ en orden de izquierda a derecha, y en el extremo inferior de la barra vertical $i$ hay escrito un entero positivo $s_i$.

Figura 3-1: Ejemplo de Amidakuji ($n = 4, m = 5, s_1 = 20, s_2 = 80, s_3 = 100, s_4 = 50$)

Al recorrer el camino en orden desde la parte más alta de la barra vertical $i$, el entero escrito en el extremo inferior al que se llega es la puntuación obtenida al elegir la barra vertical $i$. Por ejemplo, en la Figura 3-1, al elegir la barra vertical $1$ la puntuación es de $80$ puntos, y al elegir la barra vertical $2$ la puntuación es de $100$ puntos.

Figura 3-2: Ejemplo de cómo recorrer los caminos

J-kun ha decidido elegir las $k$ barras verticales consecutivas desde la barra vertical $1$ hasta la barra vertical $k$. La suma de las puntuaciones al elegir esas $k$ barras verticales será la puntuación de J-kun. Sin embargo, puedes elegir una barra horizontal del Amidakuji y eliminarla del Amidakuji (o también puedes optar por no eliminar ninguna). Si eliminas una barra horizontal, la puntuación de J-kun será la suma de las puntuaciones al elegir las $k$ barras verticales consecutivas desde la barra vertical $1$ hasta la barra vertical $k$ en el Amidakuji tras la eliminación.

Dada la forma del Amidakuji y la cantidad $k$ de barras verticales que elige J-kun, escribe un programa para hallar el valor mínimo posible de la puntuación de J-kun.

Entrada

• En la $1$-a línea hay $4$ enteros $n, m, h, k$ separados por espacios. $n$ ($2 \le n \le 1000$) representa el número de barras verticales, $m$ ($1 \le m \le 100000$) el número de barras horizontales, $h$ ($2 \le h \le 1000$) la longitud de las barras verticales y $k$ ($1 \le k \le n$) el número de barras verticales que elige J-kun.
• En las siguientes $n$ líneas están escritas las puntuaciones en los extremos inferiores de las barras verticales. En la línea $(i + 1)$ ($1 \le i \le n$) hay un entero positivo $s_i$. Además, se cumple $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$.
• En las siguientes $m$ líneas están las posiciones de las barras horizontales. Las barras horizontales están numeradas de $1$ a $m$. En la línea $(i + n + 1)$ ($1 \le i \le m$) hay $2$ enteros $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) separados por un espacio que representan la posición de la barra horizontal $i$: la barra horizontal $i$ conecta la barra vertical $a_i$ con la barra vertical $a_i + 1$, y su distancia desde el extremo superior es $b_i$. Ningún par de $2$ barras horizontales comparte un extremo.

De los datos de prueba, para el $20\%$ de la puntuación, la puntuación de J-kun es mínima cuando no se elimina ninguna barra horizontal. Además, el $30\%$ de la puntuación cumple $n \le 20, m \le 30, h \le 10$, y el $60\%$ de la puntuación cumple $m \le 1000$.

Salida

Imprime $1$ sola línea que contenga únicamente el valor mínimo posible de la puntuación de J-kun.

Sample 1

4 5 7 2
20
80
100
50
1 1
2 6
2 3
1 5
3 1

100

Sample 2

2 2 5 1
10
20
1 1
1 3

10

Explicación de los ejemplos

El Ejemplo 1 corresponde a la Figura 3-1, y la puntuación de J-kun se minimiza cuando eliminas la barra horizontal $4$ (la barra horizontal que conecta la barra vertical $1$ y la barra vertical $2$ a una distancia de $5$ desde el extremo superior). En el Ejemplo 2, la puntuación de J-kun se minimiza cuando no eliminas ninguna barra horizontal (véase la Figura 3-3).

Figura 3-3