1579: 【提高】买衣服

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

不知道是拔河训练的作用还是那个梦的缘故,反正小X是一天天瘦下来了,虽然还没有中天学长那么帅,但比起 Q 老师已经瘦了很多,小X原先买的衣服都嫌大了,于是他想去买些新衣服,小X的衣服原先一直是在非主流服装店买的,他的衣服一般店里是买不到的,而去非主流服装店肯定能买到,如膝盖上挖了两个洞的牛仔裤,正常人穿了像雨衣的冲锋衣等应有尽有,并且每买一件就送一张优惠券,小X这些年下来积聚了好多张优惠券,这次非主流服装店恰好举行优惠活动,用优惠券购买衣服可享受优惠价!
小X来到了非主流服装店,他看上了 n 件衣服,每一件衣服价格为 Pi,小X现在手中共有 m 个单位的现金,以及 k 张优惠卷。小X可以在购买某件衣服时,使用至多一张优惠券,若使用优惠券,则该衣服的价格会下降至 Qi,小X想知道他最多可以买几件衣服。

输入

第一行包含三个用空格隔开的正整数 n,k,m,依次表示衣服总数和优惠券数量及现金总数。
接下来 n 行每行包含两个整数 Pi,Qi,表示该件衣服的价格和优惠价。数据保证 Pi>=Qi。

输出

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

样例输入 复制

4 1 7
3 2
2 2
8 1
4 3

样例输出 复制

3

提示

【样例解释】

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

【数据范围】
30%的数据,n<=5,k=1,m<=100
对于另外10%的数据,n<=5,k<=5,m<=100
60%的数据,n<=200,k<=200
80%的数据,n<=2500,k<=2500

100%的数据,n<=50000,k<=50000,m<=10^16

【来源】

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

来源/分类