【题目描述】

生产某种产品需要 $N$ 道工序，编号为 $1,2,\dots,N$。

对于每道工序 $i$，有两种类型的机器 $S_i$ 和 $T_i$ 可供购买以处理该工序。

• 机器 $S_i$：每台每天可处理 $A_i$ 件产品，每台价格为 $P_i$ 元。
• 机器 $T_i$：每台每天可处理 $B_i$ 件产品，每台价格为 $Q_i$ 元。

你可以购买任意数量的每种机器，也可以不购买。

假设工序 $i$ 在引入机器后每天能处理 $W_i$ 件产品。
这里，我们将生产能力定义为 $W$ 的最小值，即 $\displaystyle \min^{N}_{i=1} W_i$。

给定总预算为 $X$ 元，求可达到的最大生产能力。

【输入格式】

第一行两个正整数 $N,X$，分别代表工序总数和总预算金额

接下来 $N$ 行，每行四个整数 $A_i,P_i,B_i,Q_i$，分别代表第 $i$ 个工序对应的两种机器的相关参数。

【输出格式】

输出一行一个整数，代表最大生产能力

【样例 1】

3 22
2 5 3 6
1 1 3 3
1 3 2 4

4

【样例 1 解释】

例如，按如下方式引入机器，可实现最大生产能力为 $4$。

• 对于工序 $1$，引入 $2$ 台机器 $S_1$。
  • 每天可加工 $4$ 个产品，共花费 $10$ 元。
• 对于工序 $2$，引入 $1$ 台机器 $S_2$ 和 $1$ 台机器 $T_2$
  • 每天可加工 $4$ 个产品，共花费 $4$ 元。
• 对于工序 $3$，引入 $2$ 台机器 $T_3$。
  • 每天可加工 $4$ 个产品，共花费 $8$ 元。

【样例 2】

1 10000000
100 1 100 1

1000000000

【样例 3】

1 1
1 10000000 1 10000000

0

【样例 3 解释】

可能存在无法实现正产能的情况。

【样例 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

894742

【数据规模与约定】

对于全部的测试点，保证：

• $1 \le N \le 100$
• $1 \le A_i,B_i \le 100$
• $1 \le P_i,Q_i,X \le 10^7$