BOJ 8372 Conference - Rectification

문제 링크:

문제 내용

컨퍼런스에서 $m$개의 발표를 진행하려고 합니다. 발표는 한 번에 $k$명이 들어갈 수 있는 발표장에서 진행되며, 발표장 1개를 빌리는 비용은 $s$입니다. 하나의 발표를 듣고자 하는 사람의 수 $x$가 $k$보다 클 경우에는 발표장 $\lceil \frac{x}{k} \rceil$개를 빌려야 하며, 여러 개의 발표를 진행하기 위해서는 각각의 발표에 필요한 발표장의 개수의 합만큼을 빌려야 합니다.

$i$번째 발표의 티켓 값은 $c_i$입니다. $c_i \times \lfloor \frac{k}{2} \rfloor \ge s$임이 보장됩니다. 즉, 한 발표장에 들어갈 수 있는 사람 수의 절반 이상을 채우면 절대 손해를 보지 않습니다.

$l$개의 단체가 발표를 듣기 위해 티켓을 예매했습니다. 이들 단체 중 일부의 예매를 취소하여 컨퍼런스가 얻는 이익이 최대가 되게 하세요. 어떤 단체 내에서 티켓의 일부만을 취소할 수는 없습니다.

입력

첫 줄에는 발표의 수 $m$, 예약한 단체의 수 $l$, 발표장의 크기 $k$, 발표장 1개를 빌리는 비용 $s$가 주어집니다. ($1 \le m \le 100$, $2 \le l \le 10^6$, $2 \le k \le 400$, $1 \le s \le 1000$)

다음 줄에는 각 발표의 티켓 한 장의 가격 $c_i$를 의미하는 $m$개의 수가 주어집니다. ($c_i \le s$)

다음 $l$줄에는 $i$번째 단체가 예약한 발표 번호 $p_i$와 티켓 수 $r_i$가 주어집니다. ($1 \le p_i \le m$, $1 \le r_i \le 1000$)

출력

최대 이익을 출력합니다.

문제 풀이