题目描述

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

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

输入格式

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

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

输出格式

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

样例输入

3 10
2 1
3 1
5 1

样例输出

6

提示

$1 \leq n \leq 100$。

$1 \leq m, w \leq 100000$。

$1 \leq c \leq 1000$。

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