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

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

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

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

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

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

样例解释

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

USACO09OCT