Bytetown 正在筹备一年一度的 Great Bitonic 会议。会议将举办 $m$ 场讲座，按照惯例，这些讲座必须在同一时间进行。所有讲座都在相同的房间内举行，每个房间最多可容纳 $k$ 人。会议有足够的房间容纳所有参与者。如果某场讲座的参与人数超过 $k$，组织者必须为该讲座预订多个房间（准确地说，对于 $n$ 名参与者，需要 $\lceil n/k \rceil$ 个房间）。

会议组织者希望最大化他们的收益——即门票销售总额减去房间租赁成本后的净利润。租赁一个可容纳 $k$ 人的房间成本为 $s$。第 $i$ 场讲座的单张门票价格为 $c_i$。门票价格的设定使得租赁一个房间容纳 $\lfloor k/2 \rfloor$ 人是有利可图的（当然，租赁房间容纳更少的人也是可能的，但不一定有利可图），这意味着在这种情况下利润是非负的。组织者可以取消部分预订，以实现收益最大化。你负责实现最初的注册系统，因此执行取消预订的过程是你的任务。

注：符号 $\lceil x \rceil$ 表示不小于 $x$ 的最小整数。类似地，$\lfloor x \rfloor$ 表示不大于 $x$ 的最大整数。

任务

编写一个程序：

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

输入格式

标准输入的第一行包含四个整数：$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

83

说明 1

对于上述样例，为了最大化收益，应取消第二个预订中的 3 张门票。