Maximizing Toxic Contest Score

You are given \( n \) toxic problems, each with a toxicity value \( a_i \) and a required time \( x_i \) to prepare its data. You have a total of \( m \) time and \( k \) teachers. Each teacher must double the toxicity of one selected problem (each problem can be doubled at most once). However, your parents will remove exactly one problem from the set you ultimately choose. You control which problem each teacher doubles and which problem is removed (the removal is forced but you can choose the target).

The contest proceeds as follows:

• You choose a subset \( S \) of the problems such that the sum of required times satisfies \( \sum_{i\in S} x_i \le m \). (Note: if \( k > 0 \), you must select at least \( k \) problems because each teacher must act on a distinct problem.)
• Each teacher doubles the toxicity of one problem in \( S \). That is, if a problem \( i \) is doubled, its toxicity becomes \( 2a_i \); if it is not doubled, its toxicity remains \( a_i \). Each problem can be doubled at most once.
• Your parents then remove exactly one problem from \( S \). Optimally, you will choose to remove the problem that results in the smallest loss, so you plan to leave the problem with the smallest toxicity undoubled if possible.

Thus, if \( S \) initially has \( s \) problems and the smallest toxicity in \( S \) is \( a_{min} \), then by applying an optimal teacher assignment the final score is computed as follows:

[ \text{score} = \begin{cases} 2\sum_{i\in S} a_i - a_{min}, & \text{if } s > k, \[6mm] 2\sum_{i\in S} a_i - 2a_{min}, & \text{if } s = k. \end{cases} ]

In the special case when \( k = 0 \) (i.e. no teacher doubling), the final score is simply the sum of the toxicities minus the removed problem: \( \sum_{i\in S} a_i - a_{min} \).

Your task is to select the subset \( S \) and decide the teacher operations and which problem to remove so as to maximize the final score.

inputFormat

The first line contains three integers \( n \), \( m \), and \( k \) (the number of problems, the total available time, and the number of teachers). Each of the next \( n \) lines contains two integers \( a_i \) and \( x_i \) representing the toxicity and required time for the \( i^{th} \) problem.

outputFormat

Output a single integer, the maximum final toxicity score achievable.

sample

3 10 1
5 3
3 4
7 6

19