English · Original
Chinese · Translation
Formal · Original
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).
<center></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.
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.
## Input
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.
## Output
Print the minimum amount of energy they need, in the first and only line of output.
[samples]
众所周知，Dart 是来自颠倒世界的一种生物。为简化起见，我们称它们为 _pollywogs_。Dart 和另外 #cf_span[x - 1] 只 pollywog 正在玩一个游戏。有 #cf_span[n] 块石头排成一行，从左到右编号为 #cf_span[1] 到 #cf_span[n]。每块石头上最多只能有一只 pollywog。初始时，pollywogs 坐在前 #cf_span[x] 块石头上（每块石头上一只）。
Dart 和他的朋友们希望最终到达最后 #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] 单位能量。
此外，有 #cf_span[q] 块石头是 _特殊的_。每次落在特殊石头 #cf_span[p] 上时，会额外消耗 #cf_span[wp] 单位能量（除了跳跃消耗的能量）。#cf_span[wp] 可能为负数，此时表示 pollywog 会吸收 #cf_span[|wp|] 单位能量。
pollywogs 希望尽可能少地消耗能量（该值可能为负）。
它们只是 pollywogs，所以向你求助。请告诉它们，在最优移动情况下，它们的总能量变化是多少。
输入的第一行包含四个整数 #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)]）——pollywogs 的数量、最大跳跃长度、石头数量和特殊石头数量。
下一行包含 #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] 互不相同。
请在第一行且仅一行中输出它们所需的最小能量值。
## Input
输入的第一行包含四个整数 #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)]）——pollywogs 的数量、最大跳跃长度、石头数量和特殊石头数量。下一行包含 #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] 互不相同。
## Output
请在第一行且仅一行中输出它们所需的最小能量值。
[samples]
**Definitions**
Let $ x, k, n, q \in \mathbb{Z} $ with $ 1 \leq x \leq k \leq 8 $, $ k \leq n \leq 10^8 $, $ 0 \leq q \leq \min(25, n - x) $.
Let $ C = (c_1, c_2, \dots, c_k) \in \mathbb{Z}_{>0}^k $ be the cost vector for jumps of distance $ 1 $ to $ k $.
Let $ 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 $.
There are $ x $ pollywogs initially occupying stones $ 1, 2, \dots, x $. The goal is to move them to stones $ n - x + 1, n - x + 2, \dots, n $, one per stone.
Each jump from stone $ i $ to $ i + d $ (where $ 1 \leq d \leq k $) costs $ c_d $, and if $ i + d \in S $, an additional cost $ w(i + d) $ is incurred.
**Constraints**
- At most one pollywog per stone at all times.
- Only the leftmost pollywog may move at each step.
- Movement must be sequential: after a pollywog jumps, the next leftmost becomes active.
- All pollywogs must end on the rightmost $ x $ stones.
- Jump distances are bounded: $ 1 \leq d \leq k $.
**Objective**
Minimize the total energy cost over all jumps and special stone landings, i.e., find the minimal total cost to rearrange the pollywogs from initial positions $ \{1, 2, \dots, x\} $ to final positions $ \{n - x + 1, \dots, n\} $ under the above rules.
API Response (JSON)
{
"problem": {
"name": "E. Pollywog",
"description": {
"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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF918E"
},
"statements": [
{
"statement_type": "Markdown",
"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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "众所周知，Dart 是来自颠倒世界的一种生物。为简化起见，我们称它们为 _pollywogs_。Dart 和另外 #cf_span[x - 1] 只 pollywog 正在玩一个游戏。有 #cf_span[n] 块石头排成一行，从左到右编号为 #cf_span[1] 到 #cf_span[n]。每块石头上最多只能有一只 pollywog。初始时，pollywogs 坐在前 #cf_span[x] ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ x, k, n, q \\in \\mathbb{Z} $ with $ 1 \\leq x \\leq k \\leq 8 $, $ k \\leq n \\leq 10^8 $, $ 0 \\leq q \\leq \\min(25, n - x) $. \nLet $ C = (c_1, c_2, \\dots, c_k) \\in \\mathbb{Z}_{>0}^k...",
"is_translate": false,
"language": "Formal"
}
]
}