퀴즈

퀴즈 ProgrammeringsQuiz에는 총 $N$개의 문제가 있고, 이 문제들은 $M$개의 서로 다른 분야(예를 들어 알고리즘 이론, 컴파일러 제작, Sven 지식)에 나뉘어 있다.

문제마다 배점이 다르다. 또한 어떤 분야의 모든 문제를 맞히면 보너스 $B$점을 받는다. Simone은 8학년 때부터 Programmeringsolympiaden에 참가해 왔기 때문에 모든 문제를 맞힐 수 있다.

아쉽게도 퀴즈에는 시간 제한이 있다. 틀린 답을 낸 적은 없지만, Simone은 $K$개의 문제만 풀 시간이 있다. Simone이 얻을 수 있는 최대 점수는 얼마인가?

첫째 줄에 네 정수 $1 \le N \le 1000$, $1 \le M \le N$, $1 \le K \le N$, $1 \le B \le 100\,000$이 주어진다. 다음 $N$개의 줄에는 정수 두 개씩 주어진다. 문제를 맞혔을 때 받는 점수(1과 $1\,000$ 사이의 정수)와 그 문제가 속한 분야($1$과 $M$ 사이)이다. 각 분야에는 문제가 최소 하나 있다.

얻을 수 있는 최대 점수를 한 줄에 출력한다.

첫 번째 예시에서 Simone은 분야 1의 두 문제($300 + 400 = 700$점)와 분야 2의 유일한 문제($200$점)를 푼다. 이 두 분야의 문제를 모두 풀었으므로 보너스를 두 번 받고, 합계는 $200 + 700 + 2 \cdot 1000 = 2900$점이 된다.