Description

作为创造产奶纪录的回报，Farmer John 决定开始每个星期给 Bessie 一点零花钱。

FJ 有一些硬币，一共有 $N\ (1 \le N \le 20)$ 种不同的面额。每一个面额都能整除所有比它大的面额。

他想用给定的硬币的集合，每个星期至少给 Bessie 某个零花钱的数目 $C\ (1 \le C \le 10^8)$。请帮他计算他最多能支付多少个星期的零花钱。

Input Format

第 $1$ 行：两个由空格隔开的整数：$N$ 和 $C$。

第 $2$ 到第 $N+1$ 行：每一行有两个整数表示一个面额的硬币：硬币面额 $V\ (1 \le V \le 10^8)$ 拥有的该面额的硬币数 $B\ (1 \le B \le 10^6)$。

Output Format

第 $1$ 行：一个单独的整数，表示最多能支付多少个星期的零花钱。

3 6
10 1
1 100
5 120

111

Hint

样例解释

FJ 可以用一个面额为 $10$ 的硬币一次性支付 Bessie $1$ 周，用两个面额为 $5$ 的硬币支付 Bessie $10$ 周，用一个面额为 $1$ 的硬币和一个面额为 $5$ 的硬币支付 Bessie $100$ 周。