购买商品

题目描述

李田所想要购买一些商品。市场上有 $n$ 件商品，第 $i$ 件商品价格为 $S_i$。李田所有 $K$ 张优惠券，使用优惠券购买第 $i$ 件商品时价格会降为 $A_i$，当然每件商品只能使用一次优惠券。李田所想知道花不超过 $M$ 的钱最多可以购买多少件商品？

输入格式

第 $1$ 行：三个以空格分隔的整数：$N$、$K$ 和 $M$。

第 $2$~$N+1$ 行：第 $i+1$ 行包含两个整数：$S_i$ 和 $A_i$。

输出格式

一个整数，表示可以购买的最大商品数。

样例 #1

样例输入 #1

4 1 7 
3 2 
2 2 
8 1 
4 3

样例输出 #1

3

提示

• $1 \le K \le N \le 5 \times 10^4$
• $1 \le S_i \le A_i \le 10^9$
• $1 \le M \le 10^{14}$

样例 1 解释： 有 $4$ 件商品，$1$ 张优惠券，预算为 $7$。

李田所在第 $3$ 件商品上使用优惠券，购买商品 $1$，$2$，$3$，花费 $3 + 2 + 1 = 6$ 元。