题目背景

小 T 喜欢打 CF。

题目描述

小 T 获得了预知能力，能预知自己后面 $n$ 场比赛的表现分。

下面是表现分的定义：

• 记小 T 在参加这场比赛前账号的分数是 $i$，他这场的表现分为 $j$，那么打完这场之后他的账号分数是 $i+\lfloor\frac{j-i}{4}\rfloor$ 。
• 其中 $\lfloor x\rfloor$ 表示对 $x$ 下取整，如 $\lfloor 1.9\rfloor=1,\lfloor -1.3\rfloor=-2$。

但是小 T 只有一个账号，初始分数是 $x$。他决定从未来的 $n$ 次比赛中选择不超过 $k$ 次参加，同时，这些比赛的类型不同，具体分为两类，这些类型会给出：

• division 1：不管小 T 当前的分数是多少，都可以参加。
• division 2：只有小 T 当前的分数 $< 1900$，他才能参加。
• 注意，当前的分数为这次比赛前的分数，而不是初始分数。当前的分数会随着小 T 之前选择参加比赛的策略变动而变动。

他希望自己在所有比赛结束后得分最高，请你来帮他规划一下，在最优决策下，参加完选出的比赛后能获得的最高分数是多少。

输入格式

第一行三个正整数 $n,k,x$，同题意。

接下来 $n$ 行每行两个整数 $\mathrm{type},a_i$，分别表示比赛的类型和小 C 这场比赛的表现分，其中 $\mathrm{type}=2$ 表示是 division 2 的比赛，$\mathrm{type}=1$ 表示是 division 1 的比赛。

输出格式

一行一个数，表示答案。

2 2 1900
2 1899
2 4000

1900

2 2 1900
1 1899
2 4000

2424

提示

【样例解释 2】

两场都打。

【数据范围】

对于 $100\%$ 的数据，满足 $0\leq x,a_i\leq 4000$，$n,k\leq 5000$，$1\leq k\leq n$。