Énoncé

Vous jouez avec J-kun à l'aide d'un Amidakuji (loterie à échelles). L'Amidakuji est composé de $n$ barres verticales et de $m$ barres horizontales. Les barres verticales sont numérotées de $1$ à $n$ de gauche à droite, et à l'extrémité inférieure de la barre verticale $i$ est écrit un entier strictement positif $s_i$.

Figure 3-1 : Exemple d'Amidakuji ($n = 4, m = 5, s_1 = 20, s_2 = 80, s_3 = 100, s_4 = 50$)

En suivant le chemin depuis tout en haut de la barre verticale $i$, l'entier écrit à l'extrémité inférieure atteinte est le score obtenu lorsque l'on choisit la barre verticale $i$. Par exemple, sur la Figure 3-1, choisir la barre verticale $1$ donne un score de $80$ points, et choisir la barre verticale $2$ donne un score de $100$ points.

Figure 3-2 : Exemple de parcours des chemins

J-kun a décidé de choisir les $k$ barres verticales consécutives allant de la barre verticale $1$ à la barre verticale $k$. La somme des scores obtenus en choisissant ces $k$ barres verticales constitue le score de J-kun. Cependant, vous pouvez choisir une barre horizontale dans l'Amidakuji et la supprimer de l'Amidakuji (vous pouvez aussi choisir de n'en supprimer aucune). Si vous supprimez une barre horizontale, le score de J-kun sera la somme des scores obtenus en choisissant les $k$ barres verticales consécutives allant de la barre verticale $1$ à la barre verticale $k$ dans l'Amidakuji après suppression.

Étant donné la forme de l'Amidakuji et le nombre $k$ de barres verticales choisies par J-kun, écrivez un programme qui détermine la valeur minimale possible du score de J-kun.

Entrée

• La $1$-re ligne contient $4$ entiers $n, m, h, k$ séparés par des espaces. $n$ ($2 \le n \le 1000$) représente le nombre de barres verticales, $m$ ($1 \le m \le 100000$) le nombre de barres horizontales, $h$ ($2 \le h \le 1000$) la longueur des barres verticales, et $k$ ($1 \le k \le n$) le nombre de barres verticales choisies par J-kun.
• Les $n$ lignes suivantes contiennent les scores écrits aux extrémités inférieures des barres verticales. La $(i + 1)$-e ligne ($1 \le i \le n$) contient un entier strictement positif $s_i$. De plus, $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$ est vérifié.
• Les $m$ lignes suivantes contiennent les positions des barres horizontales. Les barres horizontales sont numérotées de $1$ à $m$. La $(i + n + 1)$-e ligne ($1 \le i \le m$) contient $2$ entiers $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) séparés par un espace, représentant la position de la barre horizontale $i$ : la barre horizontale $i$ relie la barre verticale $a_i$ et la barre verticale $a_i + 1$, et sa distance depuis l'extrémité supérieure est $b_i$. Aucune paire de $2$ barres horizontales ne partage d'extrémité commune.

Parmi les données de test, pour $20\%$ des points, le score de J-kun est minimal lorsque aucune barre horizontale n'est supprimée. De plus, $30\%$ des points vérifient $n \le 20, m \le 30, h \le 10$, et $60\%$ des points vérifient $m \le 1000$.

Sortie

Affichez $1$ seule ligne contenant uniquement la valeur minimale possible du score de 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

Explication des exemples

L'exemple 1 correspond à la Figure 3-1, et le score de J-kun est minimal lorsque vous supprimez la barre horizontale $4$ (la barre horizontale reliant la barre verticale $1$ et la barre verticale $2$ à une distance de $5$ de l'extrémité supérieure). Dans l'exemple 2, le score de J-kun est minimal lorsque vous ne supprimez aucune barre horizontale (voir la Figure 3-3).

Figure 3-3