Farmer John 需要新奶牛！有 $N$ 头待售，$1 \le N \le 50,000$，FJ 花费不能超过预算 $M$ 个货币单位，$1 \le M \le 10^{14}$。奶牛 $i$ 原价 $P_{i}$，$1 \le P_{i} \le 10^9$，但他有 $K$ 张优惠券，$1 \le K \le N$，给奶牛 $i$ 使用后价格改为 $C_{i}$，$1 \le C_{i} \le P_{i}$。每头最多用一张券。

FJ 最多买得起几头奶牛？

输入格式

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

• 第 $2..N+1$ 行：第 $i+1$ 行含两个整数 $P_{i}$、$C_{i}$。

输出格式

• 第 $1$ 行：一个整数，最多可买的奶牛数。

样例

输入格式 1

4 1 7
3 2
2 2
8 1
4 3

输出格式 1

3

说明

FJ 有 $4$ 头奶牛、$1$ 张券，预算 $7$。

他给奶牛 $3$ 用券，买下 $1$、$2$、$3$，总费用 $3 + 2 + 1 = 6$。

题目作者：Neal Wu 和 Mark Gordon，2012