Background

You are a nasty problem setter.

Problem Description

You have $n$ nasty problems. The statements are already written, but the testdata has not been prepared yet. You still have $m$ units of time. The nastiness of each problem is $a_i$, and the time needed to prepare its testdata is $x_i$. You have $k$ teachers. Each teacher can double the nastiness of one problem (each problem can be doubled at most once). Your parents strongly oppose you holding an open contest, so they have taken away one of your problems. Now you can control both the teachers' and your parents' actions, but every teacher's action and your parents' action must be carried out. What should you do to maximize the sum of nastiness of the problems you end up producing?

Input Format

The first line contains three integers: $n, m, k$.

The next $n$ lines each contain $2$ integers, $a_i, x_i$.

Output Format

Output one integer: the maximum possible sum of nastiness.

3 10 1
6 9
7 2
1 8

15

5 20 2
5 3 
9 7
2 6
7 8
1 2

38

3 6 2
5 4
3 3
3 3

12

Hint

[Sample Explanation]

Sample $1$:

You control your parents to take away $T1$. Then you prepare the testdata for $T2$ and $T3$, and also double the nastiness of $T2$. Therefore, the maximum total nastiness is $15$.

[Constraints]

For $30\%$ of the testdata, $0 \le x_i \le m$, $0 \le m \le 100$, $2 \le n \le 10$, and $k < n$.

For another $20\%$ of the testdata, it is guaranteed that $k = 0$.

For $100\%$ of the testdata, $0 \le a_i \le 1000$, $0 \le x_i \le m$, $0 \le m \le 1000$, $0 \le n \le 100$, and $k < n$.

upd in 2020.7.6: One set of hack testdata was added.

Translated by ChatGPT 5