CF917C.Pollywog

As we all know, Dart is some kind of creature from Upside Down world. For simplicity, we call their kind pollywogs. Dart and x - 1 other pollywogs are playing a game. There are n stones in a row, numbered from 1 through n from left to right. At most 1 pollywog may be sitting on each stone at a time. Initially, the pollywogs are sitting on the first x stones (one pollywog on each stone).

Dart and his friends want to end up on the last x stones. At each second, the leftmost pollywog should jump to the right. A pollywog can jump at most k stones; more specifically, a pollywog can jump from stone number i to stones i + 1, i + 2, ... i + k. A pollywog can't jump on an occupied stone. Jumping a distance i takes c__i amounts of energy from the pollywog.

Also, q stones are special Each time landing on a special stone p, takes w__p amounts of energy (in addition to the energy for jump) from the pollywog. w__p could be negative, in this case, it means the pollywog absorbs |w__p| amounts of energy.

Pollywogs want to spend as little energy as possible (this value could be negative).

They're just pollywogs, so they asked for your help. Tell them the total change in their energy, in case they move optimally.

众所周知，达特（Dart）是一种来自“颠倒世界”（Upside Down world）的生物。为简便起见，我们称其同类为“蝌蚪怪”（pollywogs）。达特与另外 $x-1$ 只蝌蚪怪正在玩一个游戏。一排共有 $n$ 块石头，从左到右依次编号为 $1$ 到 $n$。任意时刻，每块石头上最多只能坐一只蝌蚪怪。初始时，这 $x$ 只蝌蚪怪坐在最左边的 $x$ 块石头上（每块石头上恰好一只）。

达特和他的朋友们希望最终落在最右边的 $x$ 块石头上。每一秒，最左侧的蝌蚪怪必须向右跳跃一次。一只蝌蚪怪最多可跳跃 $k$ 块石头；更准确地说，若当前位于编号为 $i$ 的石头上，则可跳至石头 $i+1,\,i+2,\,\dots,\,i+k$。蝌蚪怪不能跳到已被占据的石头上。跳跃距离为 $i$ 时，需消耗该蝌蚪怪 $c_i$ 单位能量。

此外，有 $q$ 块石头是特殊的。每次降落在特殊石头 $p$ 上时，该蝌蚪怪还需额外消耗 $w_p$ 单位能量（除跳跃本身消耗外）。$w_p$ 可为负数；此时表示该蝌蚪怪将吸收 $|w_p|$ 单位能量。

蝌蚪怪们希望总能量消耗尽可能小（该值可能为负）。

它们毕竟只是蝌蚪怪，因此向你求助。请告诉它们：若采取最优移动策略，其总能量变化量是多少？

The first line of input contains four integers, x, k, n and q (1 ≤ x ≤ k ≤ 8, k ≤ n ≤ 108, 0 ≤ q ≤ min(25, n - x)) — the number of pollywogs, the maximum length of jump, the number of stones and the number of special stones.

The next line contains k integers, _c_1, _c_2, ... c__k, separated by spaces (1 ≤ c__i ≤ 109) — the energetic costs of jumps.

The next q lines contain description of the special stones. Each line contains two integers p and w__p (x + 1 ≤ p ≤ n, |w__p| ≤ 109). All p are distinct.

输入的第一行包含四个整数 $x$、$k$、$n$ 和 $q$（$1 \le x \le k \le 8$，$k \le n \le 10^8$，$0 \le q \le \min(25, n - x)$）——分别表示蝌蚪的数量、最大跳跃长度、石头的总数以及特殊石头的数量。

第二行包含 $k$ 个整数 $c_1,\,c_2,\,\dots,\,c_k$，以空格分隔（$1 \le c_i \le 10^9$）——表示各跳跃长度对应的能量消耗。

接下来的 $q$ 行描述特殊石头。每行包含两个整数 $p$ 和 $w_p$（$x + 1 \le p \le n$，$|w_p| \le 10^9$）。所有 $p$ 均互不相同。

Print the minimum amount of energy they need, in the first and only line of output.

输出他们所需的最少能量，占输出的第一行且唯一一行。