题目描述

Farmer John 准备买一些新奶牛，市场上有 $N$ 头奶牛($1 \leq N \leq 50000$)，第 $i$ 头奶牛价格为$P_i$ ($1\leq P_i \leq 10^9$)。Farmer John 有 $K$ 张优惠券，使用优惠券购买第 $i$ 头奶牛时价格会降为 $C_i$ ($1\leq C_i\leq P_i$)，每头奶牛只能使用一次优惠券。Farmer John 想知道花不超过 $M$ ($1\leq M\leq 10^{14}$)的钱最多可以买多少奶牛？

输入格式

第一行输入三个整数，表示 $N$, $K$, $M$.

接下来 $N$ 行，每行两个整数，表示 $P_i$ 和 $C_i$.

输出格式

输出一行一个整数，表示Farmer John最多能买到的奶牛的数量。

4 1 7 
3 2 
2 2 
8 1 
4 3

3

样例说明

Farmer John 有 $4$ 头奶牛, $1$ 张优惠券, 预算是 $7$ 元。

Farmer John 在第 $3$ 头奶牛身上花掉优惠券，并且买下第 $1, 2, 3$ 头奶牛，总花费为 $3 + 2 + 1 = 6$.