Verkefni

Þú ert að leika þér ásamt J-kun með Amidakuji (draugastigalottói). Amidakuji samanstendur af $n$ lóðréttumiklum stöngum og $m$ láréttum stöngum. Lóðréttu stangirnar eru númeraðar frá $1$ til $n$ í röð frá vinstri til hægri, og við neðri enda lóðréttrar stangar $i$ er skrifuð jákvæð heiltala $s_i$.

Mynd 3-1: Dæmi um Amidakuji ($n = 4, m = 5, s_1 = 20, s_2 = 80, s_3 = 100, s_4 = 50$)

Þegar leiðin er rakin í röð alveg frá efsta hluta lóðréttrar stangar $i$, þá er heiltalan sem skrifuð er við neðri endann sem komið er á stigafjöldinn þegar lóðrétt stöng $i$ er valin. Til dæmis, á Mynd 3-1, ef lóðrétt stöng $1$ er valin fást $80$ stig, og ef lóðrétt stöng $2$ er valin fást $100$ stig.

Mynd 3-2: Dæmi um hvernig leiðir eru raktar

J-kun ákvað að velja $k$ samliggjandi lóðréttar stangir frá lóðréttri stöng $1$ til lóðréttrar stangar $k$. Summa stiganna þegar þessar $k$ lóðréttu stangir eru valdar verður stigafjöldi J-kun. Hins vegar mátt þú velja eina lárétta stöng í Amidakuji og fjarlægja hana úr Amidakuji (þú mátt líka sleppa því að fjarlægja nokkra). Ef þú fjarlægir eina lárétta stöng verður stigafjöldi J-kun summa stiganna þegar $k$ samliggjandi lóðréttu stangirnar frá lóðréttri stöng $1$ til lóðréttrar stangar $k$ eru valdar í Amidakuji eftir fjarlæginguna.

Þegar lögun Amidakuji og fjöldi lóðréttra stanga $k$ sem J-kun velur eru gefin sem inntak, skrifið forrit sem finnur minnsta mögulega gildið á stigafjölda J-kun.

Inntak

• Á $1$. línu eru $4$ heiltölur $n, m, h, k$ aðskildar með bilum. $n$ ($2 \le n \le 1000$) táknar fjölda lóðréttra stanga, $m$ ($1 \le m \le 100000$) táknar fjölda láréttra stanga, $h$ ($2 \le h \le 1000$) táknar lengd lóðréttu stanganna og $k$ ($1 \le k \le n$) táknar fjölda lóðréttra stanga sem J-kun velur.
• Á næstu $n$ línum eru stigin sem skrifuð eru við neðri enda lóðréttu stanganna. Á línu $(i + 1)$ ($1 \le i \le n$) er jákvæð heiltala $s_i$. Ennfremur gildir $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$.
• Á næstu $m$ línum eru staðsetningar láréttu stanganna. Láréttu stangirnar eru númeraðar frá $1$ til $m$. Á línu $(i + n + 1)$ ($1 \le i \le m$) eru $2$ heiltölur $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) aðskildar með bili sem tákna staðsetningu láréttrar stangar $i$: lárétt stöng $i$ tengir saman lóðrétta stöng $a_i$ og lóðrétta stöng $a_i + 1$, og fjarlægð hennar frá efri endanum er $b_i$. Engar $2$ láréttar stangir deila endapunkti.

Úr prófunargögnunum gildir fyrir $20\%$ stiga að stigafjöldi J-kun er í lágmarki þegar engin lárétt stöng er fjarlægð. Einnig uppfylla $30\%$ stiga $n \le 20, m \le 30, h \le 10$, og $60\%$ stiga uppfylla $m \le 1000$.

Úttak

Prentið út $1$ línu sem inniheldur eingöngu minnsta mögulega gildið á stigafjölda 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

Skýring á dæmum

Dæmi 1 samsvarar Mynd 3-1, og stigafjöldi J-kun verður í lágmarki þegar þú fjarlægir lárétta stöng $4$ (láréttu stöngina sem tengir lóðrétta stöng $1$ og lóðrétta stöng $2$ í fjarlægð $5$ frá efri endanum). Í Dæmi 2 verður stigafjöldi J-kun í lágmarki þegar þú fjarlægir enga lárétta stöng (sjá Mynd 3-3).

Mynd 3-3