班级准备为公益书摊采购图书,预算为 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
购买单价2元的3本、单价3元的4本、单价5元的1本,共8本,花费6+12+5=23元。最便宜的9本也需要28元,超过预算,所以不能购买9本。
预算为0,所有图书单价均为正,因此一本也买不了。