HKBU ICPC Seminar 4-6

L. 奶牛优惠券

单点时限: 2.0 sec

内存限制: 256 MB

约翰需要买更多的奶牛!市场上有 $N$ 头奶牛待售,第 $i$ 头奶牛的原价是 $P_i$ 元。约翰只有 $M$ 元,不过他还有 $K$ 张优惠券。如果他在买第 $i$ 头牛的时候使用一张优惠券,那么就可以享受一个折扣价 $C_i$。每头牛只能使用一次优惠券,请问约翰最多能买多少头奶牛回家?

输入格式

第一行:三个整数 $N$,$K$ 和 $M$,$1 ≤ K ≤ N ≤ 50000$, $1 \leq M \leq 10^{14}$

第二行到第 $N + 1$ 行:第 $i + 1$ 行有两个整数 $P_i$ 和 $C_i$,$1 ≤ C_i ≤ P_i ≤ 10^9$

输出格式

单个整数:表示约翰最多能买几头牛

样例

Input
4 1 7
3 2
2 2
8 1
4 3
Output
3