{"raw_statement":[{"iden":"statement","content":"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).\n\n<center>![image](https://espresso.codeforces.com/58adc52b55b5fcbe50fe26d031d6b5df1d79fcb7.png)</center>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.\n\nAlso, _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.\n\nPollywogs want to spend as little energy as possible (this value could be negative).\n\nThey're just pollywogs, so they asked for your help. Tell them the total change in their energy, in case they move optimally."},{"iden":"input","content":"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.\n\nThe next line contains _k_ integers, _c_1, _c_2, ... _c__k_, separated by spaces (1 ≤ _c__i_ ≤ 109) — the energetic costs of jumps.\n\nThe 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."},{"iden":"output","content":"Print the minimum amount of energy they need, in the first and only line of output."},{"iden":"examples","content":"Input\n\n2 3 10 2\n1 2 3\n5 -10\n6 1000\n\nOutput\n\n6\n\nInput\n\n4 7 85 3\n17 5 28 4 52 46 6\n59 -76\n33 -69\n19 2018\n\nOutput\n\n135"}],"translated_statement":[{"iden":"statement","content":"众所周知，Dart 是来自颠倒世界的某种生物。为简化起见，我们称它们为 _pollywogs_。Dart 和 #cf_span[x - 1] 只其他 pollywog 正在玩一个游戏。有一排 #cf_span[n] 块石头，从左到右编号为 #cf_span[1] 到 #cf_span[n]。每块石头上最多只能有一只 pollywog。初始时，pollywogs 坐在前 #cf_span[x] 块石头上（每块石头上一只）。\n\nDart 和他的朋友们希望最终都到达最后 #cf_span[x] 块石头。每秒，最左边的 pollywog 必须向右跳跃。一只 pollywog 最多可以跳跃 #cf_span[k] 块石头；更具体地说，一只 pollywog 可以从第 #cf_span[i] 块石头跳到第 #cf_span[i + 1, i + 2, ... i + k] 块石头。pollywog 不能跳到已被占据的石头上。跳跃距离 #cf_span[i] 会消耗该 pollywog 的 #cf_span[ci] 单位能量。\n\n此外，有 #cf_span[q] 块石头是 _特殊的_。每次落在特殊石头 #cf_span[p] 上时，会额外消耗 #cf_span[wp] 单位能量（除了跳跃所需能量）。#cf_span[wp] 可能为负，此时表示 pollywog 吸收了 #cf_span[|wp|] 单位能量。\n\npollywogs 希望尽可能少地消耗能量（该值可能为负）。\n\n它们只是 pollywogs，因此向你求助。请告诉它们，在最优移动情况下，它们的总能量变化是多少。\n\n输入的第一行包含四个整数 #cf_span[x, k, n] 和 #cf_span[q]（#cf_span[1 ≤ x ≤ k ≤ 8]，#cf_span[k ≤ n ≤ 108]，#cf_span[0 ≤ q ≤ min(25, n - x)]）——分别表示 pollywog 的数量、最大跳跃长度、石头数量和特殊石头数量。\n\n下一行包含 #cf_span[k] 个整数 #cf_span[c1, c2, ... ck]，用空格分隔（#cf_span[1 ≤ ci ≤ 109]）——表示跳跃所需能量消耗。\n\n接下来的 #cf_span[q] 行描述特殊石头。每行包含两个整数 #cf_span[p] 和 #cf_span[wp]（#cf_span[x + 1 ≤ p ≤ n]，#cf_span[|wp| ≤ 109]）。所有 #cf_span[p] 互不相同。\n\n请在第一行且仅一行输出它们所需的最小能量值。"},{"iden":"input","content":"输入的第一行包含四个整数 #cf_span[x, k, n] 和 #cf_span[q]（#cf_span[1 ≤ x ≤ k ≤ 8]，#cf_span[k ≤ n ≤ 108]，#cf_span[0 ≤ q ≤ min(25, n - x)]）——分别表示 pollywog 的数量、最大跳跃长度、石头数量和特殊石头数量。下一行包含 #cf_span[k] 个整数 #cf_span[c1, c2, ... ck]，用空格分隔（#cf_span[1 ≤ ci ≤ 109]）——表示跳跃所需能量消耗。接下来的 #cf_span[q] 行描述特殊石头。每行包含两个整数 #cf_span[p] 和 #cf_span[wp]（#cf_span[x + 1 ≤ p ≤ n]，#cf_span[|wp| ≤ 109]）。所有 #cf_span[p] 互不相同。"},{"iden":"output","content":"请在第一行且仅一行输出它们所需的最小能量值。"},{"iden":"examples","content":"输入\n2 3 10 2\n1 2 3\n5 -10\n6 1000\n输出\n6\n\n输入\n4 7 85 3\n17 5 28 4 52 46 65\n9 -76\n33 -69\n19 2018\n输出\n135"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ x, k, n, q \\in \\mathbb{Z} $ with $ 1 \\le x \\le k \\le 8 $, $ k \\le n \\le 10^8 $, $ 0 \\le q \\le \\min(25, n - x) $.  \nLet $ C = (c_1, c_2, \\dots, c_k) \\in \\mathbb{Z}^k $, where $ c_i $ is the energy cost of a jump of length $ i $.  \nLet $ S \\subseteq \\{x+1, x+2, \\dots, n\\} $ be the set of special stones, with a function $ w: S \\to \\mathbb{Z} $, where $ w(p) $ is the energy change upon landing on special stone $ p $.\n\nLet $ x $ pollywogs initially occupy stones $ \\{1, 2, \\dots, x\\} $.  \nThe goal is to move all pollywogs to stones $ \\{n - x + 1, n - x + 2, \\dots, n\\} $, one per stone.\n\nEach move: the leftmost pollywog jumps right by $ d \\in \\{1, 2, \\dots, k\\} $, costing $ c_d $ energy, and if landing on special stone $ p $, additional cost $ w(p) $.\n\n**Constraints**  \n1. At most one pollywog per stone at all times.  \n2. A pollywog may only jump to an unoccupied stone.  \n3. Jump distance $ d \\in \\{1, \\dots, k\\} $.  \n4. Special stone effects are applied only upon landing.  \n5. All pollywogs must end on the last $ x $ stones.\n\n**Objective**  \nMinimize the total energy cost over all jumps and special stone landings, over all valid sequences of moves achieving the target configuration.","simple_statement":null,"has_page_source":false}