题目描述

一位投资者初始拥有 $m$ 元资金，面临 $n$ 个投资项目，每个项目仅可投资一次。第 $i$ 个项目需先投入成本 $c_i$ 元，项目结束后可收回全部成本，并获得 $p_i$ 元利润。若投资者资金不足 $c_i$ ，则无法投资该项目。已完成项目收回的成本与利润可用于后续项目投资。在仅能投资 $k$ 个项目的限制下，求投资者最终能积累的资金数额。

输入格式

• 第一行：三个整数 $n$、$k$、$m$ ，分别表示项目数量、可投资项目数量、初始资金。
• 第二行至第 $n + 1$ 行：每行两个整数 $c_i$ 与 $p_i$ ，表示第 $i$ 个项目的成本与利润。

输出格式

输出一个整数，即投资者最终能够积累的资金数额。

数据范围

• 对于 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$ 。

样例

输入

3 2 1
1 1
2 2
3 3

输出

4

说明：先投资第一个项目，再投资第二个项目。第三个项目虽利润最高，但在规定投资次数内无法积累足够本金进行投资。