Oppgave

Du spiller med J-kun ved hjelp av en Amidakuji (spøkelsesstigelotteri). Amidakujien består av $n$ loddrette streker og $m$ vannrette streker. De loddrette strekene er nummerert fra $1$ til $n$ i rekkefølge fra venstre mot høyre, og ved den nederste enden av loddrett strek $i$ står det et positivt heltall $s_i$.

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

Når man følger veien i rekkefølge helt øverst fra loddrett strek $i$, er heltallet som står ved den nederste enden man kommer til, poengsummen man får når man velger loddrett strek $i$. For eksempel, i Figur 3-1 gir det å velge loddrett strek $1$ en poengsum på $80$ poeng, og det å velge loddrett strek $2$ gir en poengsum på $100$ poeng.

Figur 3-2: Eksempel på hvordan man følger veiene

J-kun har bestemt seg for å velge $k$ påfølgende loddrette streker fra loddrett strek $1$ til loddrett strek $k$. Summen av poengene når man velger disse $k$ loddrette strekene, blir J-kuns poengsum. Du kan imidlertid velge én vannrett strek i Amidakujien og fjerne den fra Amidakujien (du kan også la være å fjerne noen). Hvis du fjerner én vannrett strek, blir J-kuns poengsum summen av poengene når man velger de $k$ påfølgende loddrette strekene fra loddrett strek $1$ til loddrett strek $k$ i Amidakujien etter fjerningen.

Gitt formen på Amidakujien og antallet loddrette streker $k$ som J-kun velger, skriv et program som finner den minste mulige verdien av J-kuns poengsum.

Inndata

• På linje $1$ står $4$ heltall $n, m, h, k$ adskilt med mellomrom. $n$ ($2 \le n \le 1000$) angir antall loddrette streker, $m$ ($1 \le m \le 100000$) angir antall vannrette streker, $h$ ($2 \le h \le 1000$) angir lengden på de loddrette strekene, og $k$ ($1 \le k \le n$) angir antall loddrette streker som J-kun velger.
• På de neste $n$ linjene står poengsummene som er skrevet ved de nederste endene av de loddrette strekene. På linje $(i + 1)$ ($1 \le i \le n$) står et positivt heltall $s_i$. Videre gjelder $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$.
• På de neste $m$ linjene står posisjonene til de vannrette strekene. De vannrette strekene er nummerert fra $1$ til $m$. På linje $(i + n + 1)$ ($1 \le i \le m$) står $2$ heltall $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) adskilt med mellomrom som angir posisjonen til vannrett strek $i$: vannrett strek $i$ forbinder loddrett strek $a_i$ og loddrett strek $a_i + 1$, og avstanden fra den øverste enden er $b_i$. Ingen $2$ vannrette streker deler et endepunkt.

Av testdataene gjelder det for $20\%$ av poengene at J-kuns poengsum blir minst når ingen vannrett strek fjernes. I tillegg oppfyller $30\%$ av poengene $n \le 20, m \le 30, h \le 10$, og $60\%$ av poengene oppfyller $m \le 1000$.

Utdata

Skriv ut $1$ linje som kun inneholder den minste mulige verdien av J-kuns poengsum.

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

Forklaring av eksempler

Eksempel 1 tilsvarer Figur 3-1, og J-kuns poengsum blir minst når du fjerner vannrett strek $4$ (den vannrette streken som forbinder loddrett strek $1$ og loddrett strek $2$ i avstand $5$ fra den øverste enden). I Eksempel 2 blir J-kuns poengsum minst når du ikke fjerner noen vannrett strek (se Figur 3-3).

Figur 3-3