# 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?

## Input

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.

## 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 \le 100, M = 1$ |

2 |
29 |
$M \le 5$ |

3 |
20 |
all question give the same number of points |

4 |
35 |

Sample Input 1 | Sample Output 1 |
---|---|

5 3 3 1000 300 1 400 1 200 2 200 3 300 3 |
2900 |

Sample Input 2 | Sample Output 2 |
---|---|

5 3 3 1 300 1 400 1 200 2 300 3 200 3 |
1001 |