#Pybt3314. 奶牛优惠券

    ID: 1035 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>堆二叉树赛制:ACM来源:wyfoj http://127.0.0.1

奶牛优惠券

奶牛优惠券

题目描述

约翰需要买更多的奶牛!市场上有N头奶牛待售,第i头牛的售价是PiP_i 元。约翰只有M元,不过他还有K张优惠券。如果他在买第i头牛的时候使用一张优惠券,那么就可以享受一个折扣价CiC_i 。每头牛只能使用一张优惠券,请问约翰最多能买多少头牛回家?

输入格式

第一行:三个整数:N,K和M,1 ≤ K ≤ N ≤ 50000,1 ≤ M ≤ 101410^{14}第二行到N + 1行:第i + 1行有两个整数:PiP_i 和CiC_i ,1 ≤CiC_i ≤PiP_i≤10910^9

输出格式

单个整数:表示约翰最多能买几头牛

数据范围

(原站未提供,导入后需人工补齐)

样例

4 1 7
3 2
2 2
8 1
4 3
3

(将优惠券用在第三头牛上,可以用6元买下前三头牛)