CF917C Pollywog

众所周知，Dart 是来自「颠倒世界」的一种生物。为简便起见，我们称他们为 pollywogs。Dart 和其他 $x-1$ 个 pollywog 正在玩一个游戏。有 $n$ 个石头排成一行，从左到右编号为 $1$ 到 $n$。每个时刻，每个石头上最多只允许有一个 pollywog。同一时间，前 $x$ 个石头上各有一个 pollywog（每个石头上一个）。 Dart 和他的朋友们想要最终各自到达最后 $x$ 个石头上。每一秒，最左边的 pollywog 必须向右跳。pollywog 跳跃的最大距离是 $k$，即 pollywog 可以从编号为 $i$ 的石头跳到 $i+1,i+2,…,i+k$ 任何一个石头。pollywog 不能跳到已有 pollywog 的石头上。跳跃距离 $i$ 所消耗的能量为 $c_{i}$。 另外，有 $q$ 个特殊石头。每当 pollywog 落在编号为 $p$ 的特殊石头上时，会额外消耗 $w_{p}$ 的能量（这个能量是在跳跃能量之外消耗的）。$w_{p}$ 可能是负数，表示 pollywog 会吸收 $|w_{p}|$ 的能量。 pollywogs 希望总能量消耗尽可能少（该数可能为负数）。 他们只是 pollywog，所以请求你帮忙。请告诉他们在最优化移动下的总能量变化。

输入的第一行包含四个整数，$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)$），分别表示 pollywog 的数量、最大跳跃距离、石头数量以及特殊石头的数量。 接下来一行包含 $k$ 个整数，$c_{1},c_{2},...,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$ 互不相同。

输出一个整数，表示 pollywogs 所需消耗的最小能量（总和），输出一行。

由 ChatGPT 5 翻译