你一定听说过 Great Bitonic Conference（如果没听说过，请阅读“Conference”任务的描述）。GBC 的组织者们又遇到了麻烦，他们正在寻求你的帮助。原始版本的注册系统有一个用于最大化会议收入的特殊机制。它是通过取消部分已预订的门票来实现的（这可以减少租用会议室的费用）。然而，这种做法是不可接受的。人们对会议组织者取消了单次预订中的部分门票感到不满。你需要修改注册系统，在只允许取消整笔预订的前提下，使会议的收入最大化。

编写一个程序，完成以下任务：

• 从标准输入读取门票价格、会议室容量、租用会议室的费用以及预订列表；
• 计算通过可能取消部分预订所能获得的会议最大利润；
• 将结果写入标准输出。

输入格式

标准输入的第一行包含四个整数 $m$、$l$、$k$ 和 $s$（$1 \le m \le 100$，$2 \le l \le 1\,000\,000$，$2 \le k \le 400$，$1 \le s \le 1\,000$），它们之间用单个空格分隔。它们分别代表：演讲数量、预订数量、单个会议室的容量以及租用单个会议室的费用。第二行包含 $m$ 个整数 $c_{i}$（$c_{i} \cdot \lfloor k / 2\rfloor \ge s$，$c_{i} \le s$），它们之间用单个空格分隔（$c_{i}$ 的下限是由于租用一个会议室供 $\lfloor k / 2\rfloor$ 名参会者使用时的盈利能力所决定的）。它们代表各场演讲（编号从 $1$ 到 $m$）的门票价格。接下来的 $l$ 行包含预订的描述。每项预订由两个整数 $p_{i}$ 和 $r_{i}$（$1 \le p_{i} \le m$，$1 \le r_{i} \le 1\,000$）表示，它们之间用单个空格分隔。它们分别代表演讲编号和该场演讲预订的门票数量。只允许取消同一预订中的所有门票。

输出格式

标准输出的第一行且仅包含一个整数，即通过可能取消整笔预订所能获得的总收入。

样例

输入 1

3 2 10 30
7 10 8
1 9
3 13

输出 1

77