| Codeforces Round 459 (Div. 1) |
|---|
| Закончено |
Как все знают, Дарт — это некое существо с Обратной стороны. Для простоты, мы называем их головастиками. Дарт и x - 1 других головастиков играют в игру. В ряд выложены n камней, пронумерованных от 1 до n слева направо. На одном камне одновременно может сидеть не более 1 головастика. Изначально головастики сидят на первых x камнях (по одному головастику на камне).
Дарт и его друзья хотят оказаться на последних 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 различны.
Выведите минимально возможное количество единиц энергии, которое нужно потратить головастикам.
2 3 10 2
1 2 3
5 -10
6 1000
6
4 7 85 3
17 5 28 4 52 46 6
59 -76
33 -69
19 2018
135
