问题1187--挑战

1187: 挑战

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

Miaoyao被前一款游戏的阵法困得心力交瘁,尽管在你的帮助下成功脱困而出,他仍然不想继续玩下去了。于是,他打开了另一款游戏……

当Miaoyao站在Boss面前的时候,他发现,这个Boss不能单纯靠武力战胜,而需要对自身有着精准的把控。具体来说,Boss会展开M个幻境,第i个幻境中必须恰好用i点伤害才能打破,不能多,也不能少。Miaoyao作为一名工程师,需要靠制造的道具来造成伤害。他拥有N种道具,第i种道具有Ci个,每个可以造成Wi点伤害。在每个幻境中,Miaoyao可以使用的道具数是相互独立的,即第i种道具在所有幻境当中都可以使用Ci。现在,Miaoyao想知道他能打破多少个幻境。

输入

第一行两个数n,m,含义如题目中所述。

接下来n行,第i行包含两个数wi,ci,表示第i件物品的伤害与数目。

输出

输出一个整数,表示可以打破的幻境数

样例输入 Copy

3 10
2 1
3 1
5 1

样例输出 Copy

6

提示

1<=n<=100

1<=m,w<=100000

1<=c<=1000

样例中,Miaoyao可以打破第2、3、5、7、8、10个幻境,共6个

来源/分类