优惠券

题目描述:

新学期开学了，Smart准备买一些新书，书店有N本新书，第i本新书价格为Pi，使用优惠券购买第i本书时价格会降为Ci。Smart有K张优惠券，每本新书只能使用一次优惠券。Smart想知道花不超过M的钱最多可以买多少本新书？

输入格式:

第一行三个用空格隔开的整数N,K和M；

接下来N行，每行两个整数Pi和Ci。1≤N≤50000，1≤K≤N，1≤Pi≤10^9，1≤Ci≤Pi，1≤M≤10^14。

输出格式:

输出一个整数，表示Smart最多可以购买的新书数量。

样例输入:

4 2 13
4 2
2 1
6 3
9 4

样例输出:

4

时间限制: 1000ms
空间限制: 256MB

---