34401번 - 놀이기구 줄서기

문제

민규는 친구들과 테마파크에 갔다가 한 놀이기구에서 빈 좌석을 최대한 줄이고자 작은 그룹을 먼저 찾아 태우는 모습을 보았다. 이것이 회전율을 높이기 위한 운영 방식임을 알게 된 민규는 실제로도 대기 시간이 줄어드는지 궁금해졌다.

놀이기구의 운영 방식은 다음과 같다. 해당 놀이기구에 대한 그룹들의 도착 시각과 인원이 주어진다. 각 그룹은 서로 다른 시각에 대기열에 도착한다. 이 놀이기구는 0ドル$초부터 시작하여 $P$초마다 탑승을 진행하며, 한 번에 최대 $K$명을 태울 수 있다.

탑승은 먼저 도착한 그룹부터 진행해야 하며, 각 그룹은 대기열에 도착한 시점부터 곧바로 놀이기구에 탑승할 수 있다. 단, 각 그룹은 모든 인원이 한 번에 탑승해야 한다. 따라서 본인보다 앞에 있는 모든 그룹이 현재 빈 좌석의 수보다 인원이 많다면 먼저 탑승할 수 있다. 만약 더 이상 탑승할 수 있는 그룹이 없다면, 빈 좌석이 있더라도 놀이기구는 곧바로 출발한다.

각 그룹의 대기 시간을 $($탑승 시각$)-($도착 시각$)$으로 정의했을 때, 모든 그룹의 대기 시간의 합을 구해보자.

입력

첫 번째 줄에 그룹의 수 $N,ドル 놀이기구의 탑승 간격 $P$와 인원 제한 $K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 각 그룹의 도착 시각 $t_i$와 인원 $a_i$가 공백으로 구분되어 주어진다.

출력

모든 그룹의 대기 시간의 합을 출력한다.

제한

• 1ドル \le N \le 100,000円$
• 1ドル \le P \le 500$
• 1ドル \le K \le 5$
• 0ドル \le t_i \le 1,000円,000円$
• 1ドル \le a_i \le K$
• 모든 $t_i$는 서로 다르다.
• 주어지는 모든 수는 정수이다.

힌트