时间限制：1秒　　内存限制：256M

---

【题目描述】

　　贝西工作勤勤恳恳，她每月向约翰索要 \(C\) 元钱作为工资。约翰手上有不少钱，他一共有 \(N\) 种面额的钞票。第 \(i\) 种钞票的面额记作 \(V_i\)，约翰有 \(K_i\) 张。钞票的面额设定是比较合理的，保证所有大面额的钞票都是所有小面额钞票的整数倍。假设约翰每个月给贝西发一次工资，那么这些钱够发几个月的工资呢？贝西不会找零，如果约翰发的钱大于 \(C\) 元，多余的部分就算是贝西的奖励了。

【输入格式】

　　第一行：两个整数 \(N\) 和 \(C\)。
　　第二行到第 \(N + 1\) 行：第 \(i + 1\) 行有两个整数 \(V_i\) 和 \(K_i\)。

【输出格式】

　　单个整数：表示约翰最多能给贝西发几个月的工资

【输入输出样例】

　Input

3 6
10 1
1 100
5 120

　Output

111

【输出格式说明】

　　第一个月先给一张十元的，接下来十个月每个月都给两张五元的，最后一百个月每月给一张一元的和一张五元的。

【数据限制】

　　对于 \(100\%\) 的数据，\(1 ≤ N ≤ 20\)，\(1 ≤ C ≤ 10^9\)，\(1 ≤ V_i ≤ 10^9\)，\(1 ≤ K_i ≤ 10^6\)。

【来源】

　　Mr.he