Deskripsi Masalah

Anda sedang bermain bersama J-kun menggunakan Amidakuji (undian tangga hantu). Amidakuji terdiri dari $n$ garis vertikal dan $m$ garis horizontal. Garis-garis vertikal diberi nomor dari $1$ sampai $n$ secara berurutan dari kiri ke kanan, dan pada ujung bawah garis vertikal $i$ tertulis sebuah bilangan bulat positif $s_i$.

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

Ketika menelusuri jalur secara berurutan dari ujung paling atas garis vertikal $i$, bilangan bulat yang tertulis di ujung bawah tempat berakhirnya jalur tersebut adalah skor jika memilih garis vertikal $i$. Sebagai contoh, pada Gambar 3-1, memilih garis vertikal $1$ memberikan skor $80$ poin, dan memilih garis vertikal $2$ memberikan skor $100$ poin.

Gambar 3-2: Contoh cara menelusuri jalur

J-kun memutuskan untuk memilih $k$ garis vertikal berurutan mulai dari garis vertikal $1$ sampai garis vertikal $k$. Jumlah skor ketika memilih $k$ garis vertikal tersebut menjadi skor J-kun. Akan tetapi, Anda boleh memilih satu garis horizontal di dalam Amidakuji dan menghapus garis horizontal tersebut dari Amidakuji (Anda juga boleh tidak menghapus garis horizontal mana pun). Jika Anda menghapus satu garis horizontal, maka skor J-kun adalah jumlah skor ketika memilih $k$ garis vertikal berurutan mulai dari garis vertikal $1$ sampai garis vertikal $k$ pada Amidakuji setelah penghapusan.

Diberikan bentuk Amidakuji dan banyaknya garis vertikal $k$ yang dipilih J-kun sebagai masukan, buatlah program untuk mencari nilai minimum yang mungkin dari skor J-kun.

Format Masukan

• Baris ke-$1$ berisi $4$ bilangan bulat $n, m, h, k$ yang dipisahkan oleh spasi. $n$ ($2 \le n \le 1000$) menyatakan banyaknya garis vertikal, $m$ ($1 \le m \le 100000$) menyatakan banyaknya garis horizontal, $h$ ($2 \le h \le 1000$) menyatakan panjang garis vertikal, dan $k$ ($1 \le k \le n$) menyatakan banyaknya garis vertikal yang dipilih J-kun.
• $n$ baris berikutnya berisi skor yang tertulis di ujung bawah garis vertikal. Baris ke-$(i + 1)$ ($1 \le i \le n$) berisi sebuah bilangan bulat positif $s_i$. Selain itu, berlaku $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$.
• $m$ baris berikutnya berisi posisi garis-garis horizontal. Garis horizontal diberi nomor dari $1$ sampai $m$. Baris ke-$(i + n + 1)$ ($1 \le i \le m$) berisi $2$ bilangan bulat $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) yang dipisahkan oleh spasi, yang menyatakan posisi garis horizontal $i$: garis horizontal $i$ menghubungkan garis vertikal $a_i$ dan garis vertikal $a_i + 1$, serta jarak garis horizontal $i$ dari ujung atas adalah $b_i$. Tidak ada $2$ garis horizontal yang berbagi titik ujung yang sama.

Dari data uji, untuk $20\%$ nilai, skor J-kun menjadi minimum ketika tidak ada garis horizontal yang dihapus. Selain itu, $30\%$ nilai memenuhi $n \le 20, m \le 30, h \le 10$, dan $60\%$ nilai memenuhi $m \le 1000$.

Format Keluaran

Keluarkan $1$ baris yang hanya berisi nilai minimum dari skor 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

Penjelasan Contoh

Contoh 1 sesuai dengan Gambar 3-1, dan skor J-kun menjadi minimum ketika Anda menghapus garis horizontal $4$ (garis horizontal yang menghubungkan garis vertikal $1$ dan garis vertikal $2$ pada jarak $5$ dari ujung atas). Pada Contoh 2, skor J-kun menjadi minimum ketika Anda tidak menghapus garis horizontal mana pun (lihat Gambar 3-3).

Gambar 3-3