Tehtävänanto

Pelaat J-kunin kanssa käyttäen Amidakuji-arpapeliä (haamutikkaat). Amidakuji koostuu $n$ pystysuorasta tangosta ja $m$ vaakasuorasta tangosta. Pystytangot on numeroitu vasemmalta oikealle luvusta $1$ lukuun $n$, ja pystytangon $i$ alapäähän on kirjoitettu positiivinen kokonaisluku $s_i$.

Kuva 3-1: Esimerkki Amidakujista ($n = 4, m = 5, s_1 = 20, s_2 = 80, s_3 = 100, s_4 = 50$)

Kun reittiä seurataan järjestyksessä pystytangon $i$ aivan yläpäästä alkaen, saavutetussa alapäässä lukeva kokonaisluku on pistemäärä, joka saadaan valittaessa pystytanko $i$. Esimerkiksi Kuvassa 3-1 pystytangon $1$ valitseminen antaa $80$ pistettä ja pystytangon $2$ valitseminen antaa $100$ pistettä.

Kuva 3-2: Esimerkki reitin seuraamisesta

J-kun on päättänyt valita $k$ peräkkäistä pystytankoa pystytangosta $1$ pystytankoon $k$. Näiden $k$ pystytangon valitsemisesta saatavien pisteiden summa on J-kunin pistemäärä. Voit kuitenkin valita yhden vaakasuoran tangon Amidakujista ja poistaa sen Amidakujista (tai voit olla poistamatta yhtäkään). Jos poistat yhden vaakasuoran tangon, J-kunin pistemäärä on pystytangosta $1$ pystytankoon $k$ ulottuvien $k$ peräkkäisen pystytangon valitsemisesta saatavien pisteiden summa poiston jälkeisessä Amidakujissa.

Kun syötteenä annetaan Amidakujin muoto ja J-kunin valitsemien pystytankojen lukumäärä $k$, kirjoita ohjelma, joka etsii J-kunin pistemäärän pienimmän mahdollisen arvon.

Syöte

• Rivillä $1$ on $4$ välilyönnein erotettua kokonaislukua $n, m, h, k$. $n$ ($2 \le n \le 1000$) ilmaisee pystytankojen lukumäärän, $m$ ($1 \le m \le 100000$) vaakasuorien tankojen lukumäärän, $h$ ($2 \le h \le 1000$) pystytankojen pituuden ja $k$ ($1 \le k \le n$) J-kunin valitsemien pystytankojen lukumäärän.
• Seuraavilla $n$ rivillä on pystytankojen alapäihin kirjoitetut pistemäärät. Rivillä $(i + 1)$ ($1 \le i \le n$) on positiivinen kokonaisluku $s_i$. Lisäksi pätee $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$.
• Seuraavilla $m$ rivillä on vaakasuorien tankojen sijainnit. Vaakasuorat tangot on numeroitu luvusta $1$ lukuun $m$. Rivillä $(i + n + 1)$ ($1 \le i \le m$) on $2$ välilyönnillä erotettua kokonaislukua $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$), jotka ilmaisevat vaakasuoran tangon $i$ sijainnin: vaakasuora tanko $i$ yhdistää pystytangon $a_i$ ja pystytangon $a_i + 1$, ja sen etäisyys yläpäästä on $b_i$. Mitkään $2$ vaakasuoraa tankoa eivät jaa yhteistä päätepistettä.

Testiaineistosta $20\%$ pisteistä J-kunin pistemäärä on pienimmillään, kun yhtäkään vaakasuoraa tankoa ei poisteta. Lisäksi $30\%$ pisteistä täyttää ehdot $n \le 20, m \le 30, h \le 10$, ja $60\%$ pisteistä täyttää ehdon $m \le 1000$.

Tuloste

Tulosta $1$ rivi, joka sisältää vain J-kunin pistemäärän pienimmän mahdollisen arvon.

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

Esimerkkien selitys

Esimerkki 1 vastaa Kuvaa 3-1, ja J-kunin pistemäärä on pienimmillään, kun poistat vaakasuoran tangon $4$ (vaakasuoran tangon, joka yhdistää pystytangon $1$ ja pystytangon $2$ etäisyydellä $5$ yläpäästä). Esimerkissä 2 J-kunin pistemäärä on pienimmillään, kun et poista yhtäkään vaakasuoraa tankoa (katso Kuva 3-3).

Kuva 3-3