241993 - 公益书摊采购

题目描述

班级准备为公益书摊采购图书,预算为 B 元。仓库提供 n 类图书,第 i 类每本单价为 p_i 元,最多可以买 s_i 本。

每一类都允许购买其中一部分,也允许一本不买,但只能购买整数本。没有运费、优惠或其他费用。

所有图书在这次活动中都按“本”计算贡献,不因类别或价格不同而获得额外收益。请计算总花费不超过预算时,最多可以买多少本图书。不要求花完预算,也不要求每类都购买。

输入

第一行包含两个整数 n,B。

接下来 n 行,每行包含两个整数 p_i,s_i,表示该类单价和库存。类别不保证按价格排序,允许不同类别单价相同,允许库存为0。

【数据范围】

对全部数据,1\le n\le10000,0\le B\le10^9,1\le p_i\le10000,0\le s_i\le10000。

输出

输出一个整数,表示最多购买的总本数。

样例

输入

4 23
5 4
2 3
3 4
8 2

输出

8

输入

3 0
1 5
2 0
10 3

输出

0
说明

【样例解释1】

购买单价2元的3本、单价3元的4本、单价5元的1本,共8本,花费6+12+5=23元。最便宜的9本也需要28元,超过预算,所以不能购买9本。

【样例解释2】

预算为0,所有图书单价均为正,因此一本也买不了。

标签
题目参数
时间限制 2 秒
内存限制 256 MB
提交次数 6
通过人数 3
金币数量 3 枚
难度 基础


上一题 下一题