Pollywog

우리 모두 알다시피 Dart는 Upside Down 세계에서 온 어떤 생물이다. 편의상 이들의 종족을 pollywog라고 부른다. Dart와 다른 pollywog x - 1마리가 게임을 하고 있다. 일렬로 놓인 n개의 돌이 있으며, 왼쪽부터 오른쪽까지 1부터 n까지 번호가 매겨져 있다. 어느 때든 각 돌에는 최대 1마리의 pollywog만 앉을 수 있다. 처음에 pollywog들은 맨 앞의 x개 돌에 앉아 있다(각 돌에 한 마리씩 앉아 있다).

Dart와 친구들은 마지막 x개 돌에 도착하려 한다. 매초 가장 왼쪽에 있는 pollywog가 오른쪽으로 점프해야 한다. pollywog는 최대 k개의 돌만큼 점프할 수 있다. 더 구체적으로, pollywog는 번호가 i인 돌에서 i + 1, i + 2, ... i + k번 돌로 점프할 수 있다. pollywog는 이미 다른 pollywog가 있는 돌로 점프할 수 없다. 거리 i만큼 점프하면 그 pollywog의 에너지가 ci만큼 소모된다.

또한 q개의 돌은 특별하다 특별한 돌 p에 착지할 때마다, 그 pollywog의 에너지가 wp만큼 소모된다(점프에 필요한 에너지에 추가된다). wp는 음수일 수도 있으며, 이 경우 pollywog가 |wp|만큼의 에너지를 흡수한다는 뜻이다.

pollywog들은 가능한 한 적은 에너지를 소모하려 한다(이 값은 음수일 수도 있다).

그들은 그저 pollywog이므로 여러분에게 도움을 요청했다. 최적으로 이동할 경우 에너지의 총 변화량을 알려 주자.

입력의 첫 번째 줄에 네 정수 x, k, n, q이 주어진다(1 ≤ x ≤ k ≤ 8, k ≤ n ≤ 108, 0 ≤ q ≤ min(25, n - x)) — 각각 pollywog의 수, 점프의 최대 길이, 돌의 수, 특별한 돌의 수이다.

다음 줄에는 점프의 에너지 비용을 나타내는 k개의 정수 c1, c2, ... ck가 공백으로 구분되어 주어진다 (1 ≤ ci ≤ 109).

다음 q개 줄에는 특별한 돌에 대한 설명이 주어진다. 각 줄에는 두 정수 p와 wp가 주어진다 (x + 1 ≤ p ≤ n, |wp| ≤ 109). 모든 p는 서로 다르다.

필요한 최소 에너지양을 출력의 첫 번째이자 유일한 줄에 출력한다.