|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||1024 MB||5||1||1||100.000%|
In the quiz ProgrammeringsQuiz there are $N$ questions in total, distributed over $M$ different categories (for example, algorithm theory, compiler construction or Sven knowledge).
The questions are worth different amounts of points. Additionally, you will get a bonus $B$ if you answer all questions in a certain category. Simone has participated in Programmeringsolympiaden since 8th grade, so she is able to answer all the questions.
Unfortunately, there is a time limit to the quiz. Despite never giving the wrong answer, Simone will only have time to answer $K$ questions. What is the maximum number of points she can achieve?
The first line consists of four integers $1 \le N \le 1000$, $1 \le M \le N$, $1 \le K \le N$, $1 \le B \le 100\,000$. The following $N$ lines consist of two integers each: the points given for answering the question (an integer between $1$ and $1\,000$) and which category it belongs to (between $1$ and $M$). Each category will have at least one question.
Print one line containing the maximal possible number of points.
5 3 3 1000 300 1 400 1 200 2 200 3 300 3
5 3 3 1 300 1 400 1 200 2 300 3 200 3
In the first sample Simone answers both questions from category 1 ($300 + 400 = 700$ points) and the only question in category 2 ($200$ points). Since these were the only questions in these two categories we get two bonuses, which gives a total of $200 + 700 + 2 \cdot 1000 = 2900$ points.