题目描述

为了安抚哼哈二熊，光头强决定每周给他们一定的津贴。光头强的有 $N(1≤N≤20)$ 种不同面值的硬币，任意两种面值的硬币都存在整数倍关系（例如，$1$ 元硬币、$5$ 元硬币、$10$ 元硬币和 $50$ 元硬币）。支付给二熊的金钱不得少于 $C(1≤C≤100000000)$。

请帮他计算他可以付给二熊的最大周数。

输入描述

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

第 $2..N+1$ 行：每一行对应一种硬币的面额，包含两个整数：面额的值 $V(1≤V≤1000000)$，以及光头强持有的该面额的硬币数量 $B(1≤B≤100000)$。

输出描述

第 $1$ 行：一个整数，即光头强至少可以向二熊支付津贴的周数。

3 6
10 1
1 100
5 120

111

提示

光头强希望每周支付二熊 6 元。他有 100 枚 1 元硬币、120 枚 5 元硬币和 1 枚 10 元硬币。

光头强可以用一枚 10 元硬币付二熊 $1$ 周，然后用两枚 5 元硬币付 $10$ 周，然后再用 1 元硬币和 5 元硬币付 $100$ 周。