近期发现部分用户尝试利用判题系统的评测信息进行作弊,严重破坏了公平竞争的环境。为维护良好的交流与学习氛围,已对判题机进行了优化,当程序遇到测试点不通过时会立即返回而不评测更多测试点;并且延长提交间隔为60秒。作弊行为不仅违背了学习的初衷,还侵害了其他用户的公平权益,希望所有用户能够遵守规范,专注算法与思维能力的提升。对于恶意多次尝试的用户,我们将保留进一步处置的权利。 —— Administrator

100612 - 鲨鱼的牙齿

时间限制

50 毫秒

内存限制

128 MB

通过次数

30

提交次数

119

一只鲨鱼有m排牙齿,共n颗。第i颗的活力为{c_i}。鲨鱼吃掉一个食物时会使用某一排牙齿,被使用的一排牙齿每颗活力将会降低1,鲨鱼必须保证每颗牙齿的活力不能为负。现在有k个食物,鲨鱼最多能吃到几个?

输入

第一行,有单个空格分隔的三个整数,分别表示n,m,k

接下来n行,每行有单个空格分隔的两个整数,分别表示牙齿所在行r和这颗牙齿当前的活力值{c_i}

对于100%的数据:

1\le r \le m \le n \le 1\cdot 10^5

0\le k,{c_i} \le 1\cdot 10^6

输出

一行,一个整数。

样例

输入

3 2 88
1 20
1 30
2 10

输出

30

输入

3 2 8
1 20
1 30
2 10

输出

8