Background

You are a notorious problem setter.

Problem Description

You have $n$ notorious problems prepared, with the problem statements already done but the data not yet generated. You have $m$ units of time left. Each problem has a notoriousness level of $a_i$ and requires $x_i$ units of time to generate the data. You have $k$ teachers, each of whom can double the notoriousness level of one problem (each problem can be doubled at most once). Your parents, who strongly oppose you hosting a public contest, have taken away one of your problems. You can control the actions of your teachers and parents, but each action must be executed. How should you manage these actions to maximize the total notoriousness level of the problems you will set?

Input Format

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

The following $n$ lines each contain two integers, $a_i$ and $x_i$.

Output Format

A single integer, the maximum total notoriousness level.

Sample Input and Output

Sample Input #1

3 10 1
6 9
7 2
1 8

Sample Output #1

15

Sample Input #2

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

Sample Output #2

38

Sample Input #3

3 6 2
5 4
3 3
3 3

Sample Output #3

12

Notes

Sample Explanation

Sample #1:

You control your parents to take away problem $T1$, then generate data for problems $T2$ and $T3$, and double the notoriousness level of problem $T2$. Thus, the maximum notoriousness level is $15$.

Data Range

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

For another $20\%$ of the data, $k = 0$.

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

Updated on July 6, 2020: Added a hack data set.

见题面 Input 部分

见题面 Output 部分