You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目3：

[芳乃]获得了 $k$ 张[丛雨]家咖啡馆的优惠券。丛雨家的咖啡馆今日供应 $n$ 杯咖啡，每杯咖啡有原价和优惠价。如果芳乃对某杯咖啡使用一张优惠券，就可以以优惠价购买这杯咖啡，否则她只能按原价购买。另外芳乃数了数自己钱包里的钱，有 $m$ 元，她想知道她最多能买多少杯咖啡？

输入格式（coupon.in）

第一行三个正整数 $n$ 和 $m$ 和 $k$ ，含义如上所述。 第二行到第 $n+1$ 行每行两个正整数，表示每杯咖啡的原价和优惠价。

输出格式（coupon.out）

一行一个正整数，表示最多能买多少咖啡。

输入样例

10 1000 1
162 125
143 83
142 123
257 131
295 190
191 143
289 176
192 157
143 138
103 98

输出样例

6

数据范围

对于 $30\%$ 的数据，满足 $1 \le k \le n \le 20, 1 \le m \le 100000, 1 \le 优惠价 \le 原价 \le 10000$ 。 对于 $100\%$ 的数据，满足 $1 \le k \le n \le 20000, 1 \le m \le 1000000000, 1 \le 优惠价 \le 原价 \le 1000000000$ 。