Problem

Du spelar med J-kun med hjälp av en Amidakuji (spökstegelotteri). Amidakujin består av $n$ vertikala streck och $m$ horisontella streck. De vertikala strecken är numrerade från $1$ till $n$ i ordning från vänster till höger, och vid den nedre änden av vertikalt streck $i$ står ett positivt heltal $s_i$.

Figur 3-1: Exempel på en Amidakuji ($n = 4, m = 5, s_1 = 20, s_2 = 80, s_3 = 100, s_4 = 50$)

När man följer vägen i ordning uppifrån på vertikalt streck $i$, är heltalet som står vid den nådda nedre änden poängen man får om man väljer vertikalt streck $i$. Till exempel, i Figur 3-1 ger valet av vertikalt streck $1$ poängen $80$ poäng, och valet av vertikalt streck $2$ ger poängen $100$ poäng.

Figur 3-2: Exempel på hur man följer vägarna

J-kun har bestämt sig för att välja $k$ på varandra följande vertikala streck från vertikalt streck $1$ till vertikalt streck $k$. Summan av poängen när man väljer dessa $k$ vertikala streck blir J-kuns poäng. Du får dock välja ett horisontellt streck i Amidakujin och ta bort det från Amidakujin (du kan också välja att inte ta bort något). Om du tar bort ett horisontellt streck blir J-kuns poäng summan av poängen när man väljer de $k$ på varandra följande vertikala strecken från vertikalt streck $1$ till vertikalt streck $k$ i Amidakujin efter borttagningen.

Givet Amidakujins utformning och antalet vertikala streck $k$ som J-kun väljer, skriv ett program som beräknar det minsta möjliga värdet på J-kuns poäng.

Indata

• På rad $1$ står $4$ heltal $n, m, h, k$ separerade med mellanslag. $n$ ($2 \le n \le 1000$) anger antalet vertikala streck, $m$ ($1 \le m \le 100000$) anger antalet horisontella streck, $h$ ($2 \le h \le 1000$) anger längden på de vertikala strecken och $k$ ($1 \le k \le n$) anger antalet vertikala streck som J-kun väljer.
• På de följande $n$ raderna står poängen som är skrivna vid de nedre ändarna av de vertikala strecken. På rad $(i + 1)$ ($1 \le i \le n$) står ett positivt heltal $s_i$. Dessutom gäller $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$.
• På de följande $m$ raderna står positionerna för de horisontella strecken. De horisontella strecken är numrerade från $1$ till $m$. På rad $(i + n + 1)$ ($1 \le i \le m$) står $2$ heltal $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) separerade med mellanslag som anger positionen för horisontellt streck $i$: horisontellt streck $i$ förbinder vertikalt streck $a_i$ och vertikalt streck $a_i + 1$, och dess avstånd från den övre änden är $b_i$. Inga $2$ horisontella streck delar en ändpunkt.

Av testdatan gäller för $20\%$ av poängen att J-kuns poäng blir minimal när inget horisontellt streck tas bort. Vidare uppfyller $30\%$ av poängen $n \le 20, m \le 30, h \le 10$, och $60\%$ av poängen uppfyller $m \le 1000$.

Utdata

Skriv ut $1$ rad som enbart innehåller det minsta möjliga värdet på J-kuns poäng.

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

Förklaring av exempel

Exempel 1 motsvarar Figur 3-1, och J-kuns poäng minimeras när du tar bort horisontellt streck $4$ (det horisontella streck som förbinder vertikalt streck $1$ och vertikalt streck $2$ på avståndet $5$ från den övre änden). I Exempel 2 minimeras J-kuns poäng när du inte tar bort något horisontellt streck (se Figur 3-3).

Figur 3-3