Maximizing Final Rating

Little T has acquired precognition ability, enabling him to foresee his performance scores for the next $n$ competitions. The performance score update is defined as follows:

If Little T’s current rating before a competition is $i$ and his performance score is $j$, then his rating after the competition becomes

$$i + \left\lfloor \frac{j - i}{4} \right\rfloor$$

where $\lfloor x \rfloor$ denotes the floor function (e.g., $\lfloor 1.9\rfloor = 1$, $\lfloor -1.3\rfloor = -2$).

Little T has one account with an initial rating of $x$. He can choose to participate in at most $k$ out of the upcoming $n$ competitions. The competitions are of two types:

• division1: Little T can participate regardless his current rating.
• division2: Little T can only participate if his current rating < 1900 (before the contest).

Plan a strategy for Little T to decide which competitions to participate in so that his final rating after all competitions is maximized.

inputFormat

The first line contains three integers $n$, $k$, and $x$, where $n$ is the number of upcoming competitions, $k$ is the maximum number of competitions Little T may participate in, and $x$ is his initial rating. Each of the next $n$ lines contains a string and an integer representing the competition type and the performance score $j$. The string is either "division1" or "division2".

outputFormat

Output a single integer, the maximum final rating Little T can achieve after following an optimal strategy.

sample

3 2 1800
division2 1820
division1 2000
division2 1900

1862

</p>