题目描述

$\red{X }$城的商场中，有着琳琅满目的各种商品。

一日，小$\red{X }$带着小$\red{Y }$前来购物，小$\red{Y }$一共看中了$\red{n}$件商品，每一件商品价格为$\red{Pi}$。

小$\red{X }$现在手中共有$\red{m}$个单位的现金，以及$\red{k }$张优惠券。小$\red{X }$可以在购买某件商品时，使用至多一张优惠券，若如此做，该商品的价格会下降至$\red{Qi}$。

小$\red{X }$希望旧能多地满足小$\red{Y }$的愿望，所以小$\red{X }$想要知道他至多能购买多少件商品。

输入格式

第一行包含三个整数$\red{n,k,m，}$表示商品总数，小$\red{X }$拥有的优惠券与现金总数。

接下来$\red{n}$行每行包含两个整数$\red{Pi,Qi}$。

输出格式

共一行包含一个整数，表示小$\red{X }$至多能购买的物品数。

样例

输入样例

4 1 7

3 2

2 2

8 1

4 3

输出样例

3

提示

样例解释：

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

对于所有数据，满足$\red{1<=k<=n<=5\times 10^4,1<=m<=10^{14},1<=Q_i<=P_i<=10^9}$

详细的数据范围见下表。