题目描述

不知道是拔河训练的作用还是那个梦的缘故，反正小Ｘ是一天天瘦下来了，虽然还没有中天学长那么帅，但比起 Q 老师已经瘦了很多，小Ｘ原先买的衣服都嫌大了，于是他想去买些新衣服，小Ｘ的衣服原先一直是在非主流服装店买的，他的衣服一般店里是买不到的，而去非主流服装店肯定能买到，如膝盖上挖了两个洞的牛仔裤，正常人穿了像雨衣的冲锋衣等应有尽有，并且每买一件就送一张优惠券，小Ｘ这些年下来积聚了好多张优惠券，这次非主流服装店恰好举行优惠活动，用优惠券购买衣服可享受优惠价！

小Ｘ来到了非主流服装店，他看上了 $n$ 件衣服，每一件衣服价格为 $P_i$，小Ｘ现在手中共有 $m$ 个单位的现金，以及 $k$ 张优惠卷。小Ｘ可以在购买某件衣服时，使用至多一张优惠券，若使用优惠券，则该衣服的价格会下降至 $Q_i$，小Ｘ想知道他最多可以买几件衣服。

输入格式

第一行包含三个用空格隔开的正整数 $n,k,m$，依次表示衣服总数和优惠券数量及现金总数。

接下来 $n$ 行每行包含两个整数 $P_i,Q_i$，表示该件衣服的价格和优惠价。数据保证 $P_i \le Q_i$。

输出格式

输出数据仅有一行包含一个整数，表示小 X 最多能购买的衣服数。

样例

4 1 7
3 2
2 2
8 1
4 3

3

样例解释

一种最优的购买方式是购买 $1,2,3$ 号物品，并用优惠券购买物品 $3$ ，总共花费为 $3 + 2 + 1 = 6$。

数据范围

本题共 $20$ 组测试数据。其中：

• 对于第 $1 \sim 6$ 组数据，$n \le 5, k = 1, m \le 100$；
• 对于第 $7 \sim 8$ 组数据，$n,k \le 5, m \le 100$；
• 对于第 $9 \sim 12$ 组数据，$n,k \le 200, m \le 10^{12}$；
• 对于第 $13 \sim 16$ 组数据，$n,k \le 2500, m \le 10^{16}$；
• 对于第 $17 \sim 20$ 组数据，$1 \le n \le 50000, 0 \le k \le 50000, 0 \le m \le 10^{16}, 1 \le Q_i \le P_i \le 10^9$。

来源

常州市2018“信息与未来”选拔赛