题目描述

你正在和 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