루미 알고리즘

#1383플래티넘Quiz

PO 2016 결선코딩출제 Simon Lindholm영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
116N ≤ 100, M = 1
229M ≤ 5
320all question give the same number of points
435

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

출처 표기

출처: Programmeringsolympiaden 2016년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.