As a broke university student who finally has time to go shopping for the first time in months, you decide to go on a cereal haul as motivation to actually eat breakfast next semester. At the supermarket, you see $N$ boxes of cereal, the $i$-th having a price tag of $c_i$ dollars and $t_i$ tastiness. You have a budget of $C$ dollars, and would like to maximize the total tastiness of the cereal you buy.

Money is tight though, and sometimes you have to resort to some morally questionable tricks up your sleeve to maximize the efficiency of your spending. While shopping for the cereal, you have time to sneakily swap the price tags of up to $K$ pairs of cereal boxes, one pair after another, without getting caught. Given these conditions, what is the maximum total tastiness you can achieve?

Constraints

$1\le N\le {10}^3$

$1\le C,c_i\le 2\times {10}^4$

$1\le t_i\le {10}^9$

$0\le K\le N$

Subtask 1 [40%]

$1\le N\le 200$

$0\le K\le 5$

Subtask 2 [30%]

$1\le N\le 200$

$0\le K\le 50$

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line contains $3$ integers $N$, $C$, and $K$.

The next $N$ lines each contain $2$ integers $c_i$ and $t_i$.

Output Specification

Output the maximum total tastiness after swapping up to $K$ pairs of price tags.

Sample Input

3 5 1
2 4
3 3
8 9

Sample Output

13

Explanation for Sample

We can swap the price tags of the second and third cereal boxes, then buy the first and the third boxes for a total tastiness of $13$.