영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
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?
Input
The first line consists of four integers 1 ≤ N ≤ 1000, 1 ≤ M ≤ N, 1 ≤ K ≤ N, 1 ≤ B ≤ 100000. The following N lines consist of two integers each: the points given for answering the question (an integer between 1 and 1000) and which category it belongs to (between 1 and M). Each category will have at least one question.
Output
Print one line containing the maximal possible number of points.
Grading
Your solution will be tested on several groups of test cases. To get points for a group you need to pass all the tests of that group.
| Group | Points | Constraints |
| 1 | 16 | N ≤ 100, M = 1 |
| 2 | 29 | M ≤ 5 |
| 3 | 20 | all question give the same number of points |
| 4 | 35 |
Explanation
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 · 1000 = 2900 points.
예제
예제 1
5 3 3 1000 300 1 400 1 200 2 200 3 300 3
2900
예제 2
5 3 3 1 300 1 400 1 200 2 300 3 200 3
1001