该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P3045 [USACO12FEB] Cow Coupons G

题目背景

Subtask 0 为原数据，Subtask 1,2 为 hack 数据。

题目描述

FJ 准备买一些新奶牛。市场上有 $N$ 头奶牛，第 $i$ 头奶牛价格为 $P_i$。FJ 有 $K$ 张优惠券，使用优惠券购买第 $i$ 头奶牛时价格会降为 $C_i$，当然每头奶牛只能使用一次优惠券。FJ 想知道花不超过 $M$ 的钱最多可以买多少奶牛？

输入格式

第一行包含三个整数 $N$，$K$ 和 $M$（含义见题目描述），以空格分隔。

接下来 $N$ 行，第 $i+1$ 行包含两个整数 $P_i$ 和 $C_i$，以空格分隔。

输出格式

输出仅一行，包含一个整数，为 FJ 花不超过 $M$ 的钱可以买的奶牛的最大数量。

输入输出样例 #1

输入 #1

4 1 7 
3 2 
2 2 
8 1 
4 3 

输出 #1

3 

说明/提示

样例描述

市场上有 $4$ 头奶牛，FJ 有 $1$ 张优惠券，可以花不超过 $7$ 元钱来买牛。

FJ 使用唯一的 $1$ 张优惠券来买第三头牛，然后原价买入了第一、二头牛，总花费 $3+2+1=6$。

数据范围

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