有一种商品的制造需要在工厂流水线经过 1, 2, . . . , N 的 N 个步骤，才算完成。 对于每个步骤 i，都有两种处理该步骤的机器 Si 和 Ti 可供购买：
- 机器 Si：每台可处理 Ai 个产品，每台价格为 Pi 日元。
- 机器 Ti：每台可处理 Bi 个产品，每台价格为 Qi 日元。
在每个步骤中，两种机器可以购买任意数量（包括零台）。
假设步骤 i 在引入机器后，可以处理 Wi 个需要经过步骤 i 的产品，我们把这个 Wi
定义为步骤 i 的处理量。 同时将工厂流水线的处理能力定义为所有步骤的处理量中的最小值，
。
现在问在总预算为 X 日元的情况下，工厂流水线可达到的最大处理能力是多少。
输入以以下格式从标准输入给出：
N X
A1 P1 B1 Q1
A2 P2 B2 Q2
. . .
AN PN BN QN
样例1
3 22
2 5 3 6
1 1 3 3
1 3 2 4
样例2
1 10000000
100 1 100 1
样例3
1 1
1 10000000 1 10000000
样例4
10 7654321
8 6 9 1
5 6 4 3
2 4 7 9
7 8 9 1
7 9 1 6
4 8 9 1
2 2 8 9
1 6 2 6
4 2 3 4
6 6 5 2
样例1
4
样例2
1000000000
样例3
0
样例4
894742
【数据范围】
数据约束和子任务
所有输入均为整数。
1 ≤ N ≤ 100
1 ≤ Ai
, Bi ≤ 100
1 ≤ Pi
, Qi
, X ≤ 10^7
样例解释 1
例如，通过以下方式引入机器，可以将制造能力提高到 4，这是可达到的最大值：
-
为工序 1 引入 2 台机器 S1。
- 相当于每天处理 4 个产品，总成本为 10 日元。
- 为工序 2 引入 1 台机器 S2。
- 相当于每天处理 1 个产品，总成本为 1 日元。
- 为工序 2 引入 1 台机器 T2。
- 相当于每天处理 3 个产品，总成本为 3 日元。
- 为工序 3 引入 2 台机器 T3。
- 相当于每天处理 4 个产品，总成本为 8 日元。
样例解释 3
有时可能无法获得正的制造能力。