컨퍼런스

바이트타운에서 해마다 열리는 그레이트 바이토닉 컨퍼런스 준비가 한창이다. 전통에 따라 $m$개의 발표가 모두 정확히 같은 시각에 진행된다. 모든 발표는 동일한 형태의 방에서 열리며, 방 하나에는 최대 $k$명이 들어갈 수 있다. 방은 언제나 충분히 많다. 어떤 발표에 $n$명이 참석하면 그 발표에는 $\lceil n/k \rceil$개의 방이 필요하다.

주최 측은 이익을 최대로 만들고 싶다. 이익은 티켓 판매 수입에서 방 대여 비용을 뺀 값이다. 정원이 $k$인 방 하나를 빌리는 비용은 $s$이고, $i$번째 발표의 티켓 한 장 가격은 $c_i$이다. 티켓 가격은 방을 $\lfloor k/2 \rfloor$명으로 채우기만 해도 이익이 음수가 아니도록 정해져 있다(그보다 적은 인원으로도 이익이 날 수 있다). 주최 측은 예약된 티켓 중 일부를 취소해 이익을 높일 수 있다.

티켓 가격, 방 정원, 방 대여 비용, 그리고 모든 예약이 주어질 때, 예약된 티켓 중 일부를 취소해 얻을 수 있는 최대 이익을 구하여라.

여기서 $\lceil x \rceil$는 $x$보다 작지 않은 가장 작은 정수, $\lfloor x \rfloor$는 $x$보다 크지 않은 가장 큰 정수를 뜻한다.

첫째 줄에 네 정수 $m$, $l$, $k$, $s$가 공백으로 구분되어 주어진다 ($1 \le m \le 100$, $2 \le l \le 1{,}000{,}000$, $2 \le k \le 400$, $1 \le s \le 1{,}000$). 각각 발표의 수, 예약의 수, 방 하나의 정원, 방 하나의 대여 비용이다.

둘째 줄에 $m$개의 정수 $c_1, \dots, c_m$이 주어지며, 모든 $i$에 대해 $c_i \cdot \lfloor k/2 \rfloor \ge s$이고 $c_i \le s$이다. $c_i$는 $i$번째 발표($1$번부터 $m$번까지 번호가 매겨짐)의 티켓 가격이다.

이어지는 $l$개의 줄에는 각각 두 정수 $p_i$와 $r_i$가 주어진다 ($1 \le p_i \le m$, $1 \le r_i \le 1{,}000$). 이는 $p_i$번 발표에 대한 $r_i$장의 예약을 뜻한다. 한 예약 안에서 전체가 아니라 원하는 만큼의 티켓만 취소할 수도 있다.

예약된 티켓 중 일부를 취소해 얻을 수 있는 최대 이익(티켓 수입에서 방 대여 비용을 뺀 값)을 정수 하나로 출력한다.

첫 번째 예제에는 티켓 가격이 각각 $7$, $10$, $8$인 발표 $3$개가 있고, 방 정원은 $10$, 방 대여 비용은 $30$이다. $1$번 발표에는 $9$장이 예약되어 있어 방 하나로 처리하면 이익은 $7 \cdot 9 - 30 = 33$이다. $3$번 발표에는 $13$장이 예약되어 있는데, $13$장을 모두 남기면 방이 두 개 필요하다. 대신 $10$장만 남겨 방 하나를 꽉 채우는 편이 더 이득이므로 $3$장을 취소하며, 이익은 $8 \cdot 10 - 30 = 50$이다. 전체 이익은 $33 + 50 = 83$이다.