众所周知,Dart 是一种来自颠倒世界的生物。为了简单起见,我们称它们为蝌蚪。达特和另外 x - 1 只蝌蚪正在玩游戏。有 n 块石头排成一排,从左到右编号为 1 到 n。每块石头上一次最多可坐 1 只蝌蚪。最初,蝌蚪坐在前 x 块石头上(每块石头上有一只蝌蚪)。
Dart 和他的朋友们希望最终获得最后 x 颗宝石。每一秒,最左边的蝌蚪都应该跳到右边。蝌蚪最多可以跳 k 块石头;更具体地说,蝌蚪可以从 i 号石头跳到 i + 1、i + 2、... i + k 号石头。蝌蚪不能跳到被占据的石头上。蝌蚪跳跃 i 的距离需要 ci 的能量。
另外,q 石头是特殊的 每次落在特殊石头 p 上时,都会从蝌蚪那里获取 wp 数量的能量(除了跳跃的能量)。 wp 可能为负数,在这种情况下,这意味着蝌蚪吸收 |wp|大量的能量。
蝌蚪希望花费尽可能少的能量(该值可能为负)。
他们只是蝌蚪,所以他们请求你的帮助。告诉他们能量的总变化,以防他们以最佳方式移动。
输入
输入的第一行包含四个整数,x、k、n 和 q (1 ≤ x ≤ k ≤ 8, k ≤ n ≤ 108, 0 ≤ q ≤ min(25, n - x)) — 蝌蚪的数量、跳跃的最大长度、石子的数量和特殊石子的数量。
下一行包含 k 个整数 c1, c2, ... ck,用空格分隔 (1 ≤ ci ≤ 109) – 跳跃的能量消耗。
接下来的 q 行包含特殊宝石的描述。每行包含两个整数 p 和 wp (x + 1 ≤ p ≤ n, |wp| ≤ 109)。所有 p 都是不同的。
输出
在输出的第一行也是唯一一行中打印他们所需的最小能量。
示例
输入 #1
2 3 10 2 1 2 3 5 -10 6 1000
输出 #1
6
输入 #2
4 7 85 3 17 5 28 4 52 46 6 59 -76 33 -69 19 2018
输出 #2
135