Treść zadania

Bawisz się razem z J-kunem za pomocą Amidakuji (drabinkowej loterii). Amidakuji składa się z $n$ pionowych kresek oraz $m$ poziomych kresek. Pionowe kreski są ponumerowane od $1$ do $n$ w kolejności od lewej do prawej, a na dolnym końcu pionowej kreski $i$ zapisana jest dodatnia liczba całkowita $s_i$.

Rysunek 3-1: Przykład Amidakuji ($n = 4, m = 5, s_1 = 20, s_2 = 80, s_3 = 100, s_4 = 50$)

Gdy podążamy ścieżką po kolei od samej góry pionowej kreski $i$, liczba całkowita zapisana na osiągniętym dolnym końcu jest wynikiem punktowym za wybranie pionowej kreski $i$. Na przykład na Rysunku 3-1 wybór pionowej kreski $1$ daje wynik $80$ punktów, a wybór pionowej kreski $2$ daje wynik $100$ punktów.

Rysunek 3-2: Przykład śledzenia ścieżek

J-kun postanowił wybrać $k$ kolejnych pionowych kresek od pionowej kreski $1$ do pionowej kreski $k$. Suma punktów uzyskanych przy wyborze tych $k$ pionowych kresek stanowi wynik J-kuna. Możesz jednak wybrać jedną poziomą kreskę w Amidakuji i usunąć ją z Amidakuji (możesz też nie usuwać żadnej). Jeśli usuniesz jedną poziomą kreskę, wynikiem J-kuna będzie suma punktów uzyskanych przy wyborze $k$ kolejnych pionowych kresek od kreski $1$ do kreski $k$ w Amidakuji po usunięciu.

Mając dany kształt Amidakuji oraz liczbę $k$ pionowych kresek wybieranych przez J-kuna, napisz program, który wyznaczy minimalną możliwą wartość wyniku J-kuna.

Wejście

• W $1$-szym wierszu znajdują się $4$ liczby całkowite $n, m, h, k$ oddzielone spacjami. $n$ ($2 \le n \le 1000$) oznacza liczbę pionowych kresek, $m$ ($1 \le m \le 100000$) oznacza liczbę poziomych kresek, $h$ ($2 \le h \le 1000$) oznacza długość pionowych kresek, a $k$ ($1 \le k \le n$) oznacza liczbę pionowych kresek wybieranych przez J-kuna.
• W kolejnych $n$ wierszach zapisane są punkty na dolnych końcach pionowych kresek. W wierszu $(i + 1)$ ($1 \le i \le n$) zapisana jest dodatnia liczba całkowita $s_i$. Ponadto zachodzi $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$.
• W kolejnych $m$ wierszach zapisane są pozycje poziomych kresek. Poziome kreski są ponumerowane od $1$ do $m$. W wierszu $(i + n + 1)$ ($1 \le i \le m$) znajdują się $2$ oddzielone spacją liczby całkowite $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) oznaczające pozycję poziomej kreski $i$: pozioma kreska $i$ łączy pionową kreskę $a_i$ oraz pionową kreskę $a_i + 1$, a jej odległość od górnego końca wynosi $b_i$. Żadne $2$ poziome kreski nie mają wspólnego końca.

Wśród danych testowych, dla $20\%$ punktów wynik J-kuna jest najmniejszy, gdy nie zostanie usunięta żadna pozioma kreska. Ponadto $30\%$ punktów spełnia warunki $n \le 20, m \le 30, h \le 10$, a $60\%$ punktów spełnia warunek $m \le 1000$.

Wyjście

Wypisz $1$ wiersz zawierający wyłącznie minimalną możliwą wartość wyniku J-kuna.

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

Wyjaśnienie przykładów

Przykład 1 odpowiada Rysunkowi 3-1, a wynik J-kuna jest najmniejszy, gdy usuniesz poziomą kreskę $4$ (poziomą kreskę łączącą pionową kreskę $1$ i pionową kreskę $2$ w odległości $5$ od górnego końca). W Przykładzie 2 wynik J-kuna jest najmniejszy, gdy nie usuniesz żadnej poziomej kreski (zobacz Rysunek 3-3).

Rysunek 3-3