컨퍼런스: 예약 정정

관련 문제인 "컨퍼런스"에 나온 대형 바이토닉 컨퍼런스(Great Bitonic Conference)를 기억할 것이다. 그 주최 측이 다시 도움을 청한다.

기존 등록 시스템은 이미 예약된 티켓 중 일부를 취소해 컨퍼런스 수익을 극대화했다. 참가자가 줄면 빌려야 하는 방도 줄어 비용이 낮아지기 때문이다. 하지만 참가자들은 이를 싫어한다. 하나의 예약에는 함께 예약한 여러 장의 티켓이 묶여 있는데, 기존 시스템은 한 예약의 일부만 취소하고 나머지는 남길 수 있었기 때문이다. 이제 수익은 그대로 극대화하되, 예약은 통째로만 취소할 수 있도록(한 예약의 모든 티켓을 남기거나 모두 취소) 시스템을 바꾸어야 한다.

발표는 $m$개 있다. 발표 $i$의 참가자는 각자 티켓 값 $c_i$를 낸다. 한 발표의 참가자들은 한 개당 $k$명을 수용하는 방에 앉으며, 방 하나를 빌리는 비용은 $s$이다. 발표 $i$가 참가자 $t$명을 남기면 방 $\lceil t / k \rceil$개가 필요하고, 수익은 $c_i \cdot t - s \cdot \lceil t / k \rceil$이 된다. 각 발표는 서로 독립적이다.

티켓 값, 방 수용 인원, 방 대여 비용, 예약 목록을 읽어, 예약을 통째로만 취소할 수 있을 때 얻을 수 있는 최대 총수익을 계산해 출력하는 프로그램을 작성하라.

첫째 줄에 네 정수 $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, c_2, \ldots, c_m$이 공백 하나로 구분되어 주어진다. $c_i$는 발표 $i$의 티켓 값이며, $c_i \le s$와 $c_i \cdot \lfloor k / 2 \rfloor \ge s$를 만족한다(방이 절반만 차도 이미 이득이 나도록 하는 조건이다).

이어지는 $l$개의 줄에는 각 예약이 두 정수 $p_i$와 $r_i$ ($1 \le p_i \le m$, $1 \le r_i \le 1\,000$)로 공백 하나로 구분되어 주어진다. 각각 발표 번호와 그 예약으로 잡은 티켓 수를 뜻한다. 예약은 통째로만 취소할 수 있다.

예약을 통째로만 취소해서 얻을 수 있는 최대 총수익을 정수 하나로 출력한다.