Problem Background

Xiao T enjoys playing Codeforces (CF).

Problem Description

Xiao T has acquired the ability to foresee his performance scores in the next $n$ competitions.

Here is the definition of performance score:

• Let's denote Xiao T's account score before participating in a competition as $i$, and his performance score in that competition as $j$. After the competition, his account score will be $i + \lfloor \frac{j - i}{4} \rfloor$.
• $\lfloor x \rfloor$ denotes the floor function, which rounds $x$ down to the nearest integer, e.g., $\lfloor 1.9 \rfloor = 1, \lfloor -1.3 \rfloor = -2$.

However, Xiao T only has one account with an initial score of $x$. He decides to choose no more than $k$ out of the upcoming $n$ competitions to participate in. These competitions are of different types, which will be specified:

• Division 1: Xiao T can participate regardless of his current score.
• Division 2: Xiao T can only participate if his current score is less than 1900.
• Note that the current score refers to the score before the competition, not the initial score. The current score will change based on Xiao T's previous choices of competitions.

Xiao T wants to maximize his score after all the competitions. Help him plan the optimal strategy to achieve the highest possible score after participating in the selected competitions.

Input Format

The first line contains three positive integers $n, k, x$, as described in the problem.

The next $n$ lines each contain two integers $\mathrm{type}, a_i$, representing the type of the competition and Xiao T's performance score in that competition, where $\mathrm{type} = 2$ indicates a Division 2 competition, and $\mathrm{type} = 1$ indicates a Division 1 competition.

Output Format

A single line containing one number, representing the highest score Xiao T can achieve under the optimal strategy.

Sample Input and Output

Sample Input #1

2 2 1900
2 1899
2 4000

Sample Output #1

1900

Sample Input #2

2 2 1900
1 1899
2 4000

Sample Output #2

2424

Notes/Hints

Sample Explanation 2

Participate in both competitions.

Data Range

For $100\%$ of the data, it is guaranteed that $0 \leq x, a_i \leq 4000$, $n, k \leq 5000$, and $1 \leq k \leq n$.

见题面 Input 部分

见题面 Output 部分