Problema

Stai giocando insieme a J-kun usando un Amidakuji (lotteria a scala fantasma). L'Amidakuji è composto da $n$ barre verticali e $m$ barre orizzontali. Le barre verticali sono numerate da $1$ a $n$ da sinistra a destra, e all'estremità inferiore della barra verticale $i$ è scritto un intero positivo $s_i$.

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

Quando si segue il percorso in ordine partendo dall'estremità più alta della barra verticale $i$, l'intero scritto all'estremità inferiore raggiunta è il punteggio ottenuto scegliendo la barra verticale $i$. Ad esempio, nella Figura 3-1, scegliendo la barra verticale $1$ il punteggio è $80$ punti, e scegliendo la barra verticale $2$ il punteggio è $100$ punti.

Figura 3-2: Esempio di come seguire i percorsi

J-kun ha deciso di scegliere $k$ barre verticali consecutive dalla barra verticale $1$ alla barra verticale $k$. La somma dei punteggi ottenuti scegliendo queste $k$ barre verticali costituisce il punteggio di J-kun. Tuttavia, puoi scegliere una barra orizzontale nell'Amidakuji ed eliminarla dall'Amidakuji (oppure puoi scegliere di non eliminarne alcuna). Se elimini una barra orizzontale, il punteggio di J-kun sarà la somma dei punteggi ottenuti scegliendo le $k$ barre verticali consecutive dalla barra verticale $1$ alla barra verticale $k$ nell'Amidakuji dopo l'eliminazione.

Dati in input la forma dell'Amidakuji e il numero $k$ di barre verticali scelte da J-kun, scrivi un programma che determini il valore minimo possibile del punteggio di J-kun.

Dati di input

• Nella $1$-a riga sono scritti $4$ interi $n, m, h, k$ separati da spazi. $n$ ($2 \le n \le 1000$) rappresenta il numero di barre verticali, $m$ ($1 \le m \le 100000$) il numero di barre orizzontali, $h$ ($2 \le h \le 1000$) la lunghezza delle barre verticali, e $k$ ($1 \le k \le n$) il numero di barre verticali scelte da J-kun.
• Nelle successive $n$ righe sono scritti i punteggi riportati alle estremità inferiori delle barre verticali. Nella riga $(i + 1)$ ($1 \le i \le n$) è scritto un intero positivo $s_i$. Inoltre vale $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$.
• Nelle successive $m$ righe sono scritte le posizioni delle barre orizzontali. Le barre orizzontali sono numerate da $1$ a $m$. Nella riga $(i + n + 1)$ ($1 \le i \le m$) sono scritti $2$ interi $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) separati da uno spazio che rappresentano la posizione della barra orizzontale $i$: la barra orizzontale $i$ collega la barra verticale $a_i$ e la barra verticale $a_i + 1$, e la sua distanza dall'estremità superiore è $b_i$. Nessuna coppia di $2$ barre orizzontali condivide un'estremità.

Nei dati di test, per il $20\%$ del punteggio, il punteggio di J-kun è minimo quando non viene eliminata alcuna barra orizzontale. Inoltre, il $30\%$ del punteggio soddisfa $n \le 20, m \le 30, h \le 10$, e il $60\%$ del punteggio soddisfa $m \le 1000$.

Dati di output

Stampa $1$ sola riga contenente unicamente il valore minimo del punteggio di 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

Spiegazione degli esempi

L'Esempio 1 corrisponde alla Figura 3-1, e il punteggio di J-kun è minimo quando elimini la barra orizzontale $4$ (la barra orizzontale che collega la barra verticale $1$ e la barra verticale $2$ a distanza $5$ dall'estremità superiore). Nell'Esempio 2, il punteggio di J-kun è minimo quando non elimini alcuna barra orizzontale (vedi Figura 3-3).

Figura 3-3