1579: 【编程进阶】买衣服
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
不知道是拔河训练的作用还是那个梦的缘故,反正小X是一天天瘦下来了,虽然还没有中天学长那么帅,但比起 Q
老师已经瘦了很多,小X原先买的衣服都嫌大了,于是他想去买些新衣服,小X的衣服原先一直是在非主流服装店买的,他的衣服一般店里是买不到的,而去非主流服装店肯定能买到,如膝盖上挖了两个洞的牛仔裤,正常人穿了像雨衣的冲锋衣等应有尽有,并且每买一件就送一张优惠券,小X这些年下来积聚了好多张优惠券,这次非主流服装店恰好举行优惠活动,用优惠券购买衣服可享受优惠价!
小X来到了非主流服装店,他看上了 n 件衣服,每一件衣服价格为 Pi,小X现在手中共有 m 个单位的现金,以及 k 张优惠卷。小X可以在购买某件衣服时,使用至多一张优惠券,若使用优惠券,则该衣服的价格会下降至 Qi,小X想知道他最多可以买几件衣服。
小X来到了非主流服装店,他看上了 n 件衣服,每一件衣服价格为 Pi,小X现在手中共有 m 个单位的现金,以及 k 张优惠卷。小X可以在购买某件衣服时,使用至多一张优惠券,若使用优惠券,则该衣服的价格会下降至 Qi,小X想知道他最多可以买几件衣服。
输入
第一行包含三个用空格隔开的正整数 n,k,m,依次表示衣服总数和优惠券数量及现金总数。
接下来 n 行每行包含两个整数 Pi,Qi,表示该件衣服的价格和优惠价。数据保证 Pi>=Qi。
接下来 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“信息与未来”选拔赛