题目描述

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

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

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

输入格式

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

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

输出格式

第 $1$ 行: 一个单独的整数，表示最多能给支付多少个星期至少为 $C$ 的零用钱。

3 6
10 1
1 100
5 120

111