올챙이

우리 모두 알다시피, Dart는 Upside Down 세계에서 온 어떤 생물이다. 편의상 이 종족을 올챙이라고 부른다. 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는 서로 다르다.

올챙이들에게 필요한 최소 에너지량을 출력의 첫 번째이자 유일한 줄에 출력한다.