题目描述

小爱有 $m$ 元钱，有 $n$ 个项目等待她的投资，每个项目只能投资一次。其中第 $i$ 个项目要求先支出成本 $c_i$ 元，待项目完成后，可以收回全部成本，且获得 $p_i$ 元利润，若小爱的钱不足 $c_i$，就没法投资这个项目了。

投资不必按照项目的编号顺序进行，可以用老项目收回的成本及利润支付新项目的成本。若小爱只能投资 $k$ 个项目，那么她最多可以积累多少钱呢？

输入格式

第一行：三个整数表示 $n$，$k$ 及 $m$； 接下来 $n$ 行，每行两个整数表示 $c_i$ 与 $p_i$。

输出格式

单个整数：表示最终可获得的最大钱数。

3 2 1
1 1
2 2 
3 3

4

样例解释 1

先做第一个项目再做第二个项目，第三个项目虽然赚钱最多，但小爱没时间积累足够的本金

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 100$；
• 对于 $60\%$ 的数据，$1\leq n\leq 5000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 100,000$；
• $1 \leq k \leq n$
• $1 \leq m \leq 10^9$
• $1 \leq p_i \leq 10^9$
• $1 \leq c_i \leq 10^9$