题目描述
在魔法大陆，可以通过消耗圣水来召唤英灵。具体来说，一共有 个种族的英灵，召唤第 个种族的英灵需要消耗 点圣水。每个种族的英灵都有无限只，所以可以重复召唤。
召唤出的英灵们依然拥有召唤的能力，不过也要消耗圣水。第 个种族的英灵在被召唤时，会拥有 点初始圣水，它们只能利用自身的初始圣水来召唤英灵，无法从外界进行补充。
现在，Karl 拥有 点圣水，同样无法进行补充。为了召唤出数量尽可能多的英灵，Karl 会选择最优的方式召唤英灵，并通过英灵继续召唤英灵……请问他最终能召唤出多少只英灵。
输入格式
从标准输入读入数据。
输入的第一行为两个正整数 和 。
随后 行，第 行两个整数 和 。
输出格式
输出到标准输出。
输出一行一个整数表示答案。
样例1输入
样例1输出
样例1解释
最优方案如下：
- 直接召唤 只第 个种族的英灵。
- 直接召唤 只第 个种族的英灵。
- 每只第 个种族的英灵再召唤第 、 个种族的英灵各 只。
一共召唤了 只英灵。
样例2输入
7 193
12 10
19 15
15 10
10 5
21 19
12 7
11 7
样例2输出
样例3
见题目目录下的 3.in 与 3.ans。
该样例满足特殊性质 A。
样例4
见题目目录下的 4.in 与 4.ans。
该样例满足特殊性质 B。
样例5
见题目目录下的 5.in 与 5.ans。
子任务
对于全部的测试数据，保证 ，。
| 测试点 |
|
|
特殊性质 |
|
= 2 |
\leq 1,000 |
|
|
\leq 50 |
|
\leq 5,000 |
\leq 5,000 |
A |
|
B |
|
|
|
\leq 10^5 |
A |
|
B |
|
|