Aufgabenstellung

Sie spielen zusammen mit J-kun mit einem Amidakuji (Geisterleiter-Lotterie). Das Amidakuji besteht aus $n$ vertikalen Stäben und $m$ horizontalen Stäben. Die vertikalen Stäbe sind von links nach rechts von $1$ bis $n$ nummeriert, und am unteren Ende des vertikalen Stabs $i$ steht eine positive ganze Zahl $s_i$.

Abbildung 3-1: Beispiel für ein Amidakuji ($n = 4, m = 5, s_1 = 20, s_2 = 80, s_3 = 100, s_4 = 50$)

Wenn man dem Weg vom obersten Ende des vertikalen Stabs $i$ aus der Reihe nach folgt, ist die am erreichten unteren Ende stehende ganze Zahl die Punktzahl, die man erhält, wenn man den vertikalen Stab $i$ wählt. In Abbildung 3-1 erhält man beispielsweise bei Wahl des vertikalen Stabs $1$ eine Punktzahl von $80$ Punkten und bei Wahl des vertikalen Stabs $2$ eine Punktzahl von $100$ Punkten.

Abbildung 3-2: Beispiel für das Verfolgen der Wege

J-kun hat beschlossen, die $k$ aufeinanderfolgenden vertikalen Stäbe von Stab $1$ bis Stab $k$ zu wählen. Die Summe der Punktzahlen bei Wahl dieser $k$ vertikalen Stäbe ist J-kuns Punktzahl. Sie dürfen jedoch einen horizontalen Stab im Amidakuji auswählen und diesen aus dem Amidakuji entfernen (Sie müssen aber keinen entfernen). Wenn Sie einen horizontalen Stab entfernen, ist J-kuns Punktzahl die Summe der Punktzahlen bei Wahl der $k$ aufeinanderfolgenden vertikalen Stäbe von Stab $1$ bis Stab $k$ im Amidakuji nach dem Entfernen.

Schreiben Sie ein Programm, das bei gegebener Form des Amidakuji und der Anzahl $k$ der von J-kun gewählten vertikalen Stäbe den minimal möglichen Wert für J-kuns Punktzahl berechnet.

Eingabe

• In der $1$. Zeile stehen $4$ durch Leerzeichen getrennte ganze Zahlen $n, m, h, k$. $n$ ($2 \le n \le 1000$) gibt die Anzahl der vertikalen Stäbe an, $m$ ($1 \le m \le 100000$) die Anzahl der horizontalen Stäbe, $h$ ($2 \le h \le 1000$) die Länge der vertikalen Stäbe und $k$ ($1 \le k \le n$) die Anzahl der von J-kun gewählten vertikalen Stäbe.
• In den folgenden $n$ Zeilen stehen die an den unteren Enden der vertikalen Stäbe notierten Punktzahlen. In der $(i + 1)$. Zeile ($1 \le i \le n$) steht eine positive ganze Zahl $s_i$. Zudem gilt $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$.
• In den folgenden $m$ Zeilen stehen die Positionen der horizontalen Stäbe. Die horizontalen Stäbe sind von $1$ bis $m$ nummeriert. In der $(i + n + 1)$. Zeile ($1 \le i \le m$) stehen $2$ durch ein Leerzeichen getrennte ganze Zahlen $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$), die die Position des horizontalen Stabs $i$ angeben: Der horizontale Stab $i$ verbindet den vertikalen Stab $a_i$ und den vertikalen Stab $a_i + 1$, und sein Abstand vom oberen Ende beträgt $b_i$. Keine $2$ horizontalen Stäbe haben einen gemeinsamen Endpunkt.

Bei den Testdaten wird für $20\%$ der Punkte J-kuns Punktzahl minimal, wenn kein horizontaler Stab entfernt wird. Außerdem erfüllen $30\%$ der Punkte $n \le 20, m \le 30, h \le 10$, und $60\%$ der Punkte erfüllen $m \le 1000$.

Ausgabe

Geben Sie $1$ Zeile aus, die nur den minimal möglichen Wert von J-kuns Punktzahl enthält.

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

Erläuterung der Beispiele

Beispiel 1 entspricht Abbildung 3-1, und J-kuns Punktzahl wird minimal, wenn Sie den horizontalen Stab $4$ (den horizontalen Stab, der die vertikalen Stäbe $1$ und $2$ im Abstand $5$ vom oberen Ende verbindet) entfernen. In Beispiel 2 wird J-kuns Punktzahl minimal, wenn Sie keinen horizontalen Stab entfernen (siehe Abbildung 3-3).

Abbildung 3-3