題目描述

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

输入格式

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

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

输出格式

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

样例

4 1 7
3 2
2 2
8 1
4 3

3

样例解释

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

数据范围

注意 本题目数据未完全按照如下放置数据点，但是保证每个部分数据都至少有一个，之后会考虑加强数据。

• subtasks1:数据没有问题
• subtasks2:假设是原题数据，有问题

30%的数据，$n\leqslant 5，k=1，m\leqslant 100$

对于另外10%的数据，$n\leqslant 5，k\leqslant 5，m\leqslant 100$

60%的数据，$n\leqslant 200，k\leqslant 200$

80%的数据，$n\leqslant 2500，k\leqslant 2500$

100%的数据，$1\leqslant n\leqslant 50000，1\leqslant k\leqslant 50000，0\leqslant m\leqslant 10^{16},0\leq Q_i \leq P_i\leq 10^4$。