題目描述

你正在和 J 君一起玩阿彌陀籤（鬼腳圖）。阿彌陀籤由 $n$ 根豎線和 $m$ 根橫線組成。豎線從左到右依次編號為 $1$ 到 $n$，在豎線 $i$ 的下端寫有正整數 $s_i$。

圖 3-1：阿彌陀籤的例子（$n = 4, m = 5, s_1 = 20, s_2 = 80, s_3 = 100, s_4 = 50$）

從豎線 $i$ 的最上端開始依次沿著路線往下走，最終到達的下端所寫的整數就是選擇豎線 $i$ 時的得分。例如，在圖 3-1 中，選擇豎線 $1$ 時得分為 $80$ 分，選擇豎線 $2$ 時得分為 $100$ 分。

圖 3-2：走法的例子

J 君決定選擇從豎線 $1$ 到豎線 $k$ 的連續 $k$ 根豎線。選擇這 $k$ 根豎線時的分數之和即為 J 君的得分。不過，你可以從阿彌陀籤中選擇一根橫線，並將該橫線從阿彌陀籤中刪去（也可以不刪去任何橫線）。如果你刪去了一根橫線，則在刪去後的阿彌陀籤中，選擇從豎線 $1$ 到豎線 $k$ 的連續 $k$ 根豎線時的分數之和即為 J 君的得分。

給定阿彌陀籤的形狀以及 J 君選擇的豎線根數 $k$，請撰寫程式，求出 J 君得分的最小值。

輸入格式

• 第 $1$ 行包含以空格分隔的 $4$ 個整數 $n, m, h, k$。$n$（$2 \le n \le 1000$）表示豎線的根數，$m$（$1 \le m \le 100000$）表示橫線的根數，$h$（$2 \le h \le 1000$）表示豎線的長度，$k$（$1 \le k \le n$）表示 J 君選擇的豎線根數。
• 接下來的 $n$ 行包含豎線下端所寫的分數。第 $(i + 1)$ 行（$1 \le i \le n$）包含一個正整數 $s_i$。此外，滿足 $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$。
• 接下來的 $m$ 行包含橫線的位置。橫線編號為 $1$ 到 $m$。第 $(i + n + 1)$ 行（$1 \le i \le m$）包含以空格分隔的 $2$ 個整數 $a_i, b_i$（$1 \le a_i \le n - 1, 1 \le b_i \le h - 1$），表示橫線 $i$ 的位置：橫線 $i$ 連接豎線 $a_i$ 與豎線 $a_i + 1$，且橫線 $i$ 距離上端的距離為 $b_i$。任意 $2$ 根橫線都不會共用端點。

在測試資料中，佔總分 $20\%$ 的資料滿足在不刪去橫線的情況下 J 君的得分最小。此外，佔總分 $30\%$ 的資料滿足 $n \le 20, m \le 30, h \le 10$，佔總分 $60\%$ 的資料滿足 $m \le 1000$。

輸出格式

輸出僅一行，只包含 J 君得分的最小值。

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

範例說明

範例 1 對應圖 3-1，當你刪去橫線 $4$（在距離上端為 $5$ 的位置連接豎線 $1$ 和豎線 $2$ 的橫線）時，J 君的得分最小。在範例 2 中，當你不刪去任何橫線時，J 君的得分最小（參見圖 3-3）。

圖 3-3