21327번 - Quiz 다국어

문제

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.

제한

힌트

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.