题目描述

有一种商品的制造需要在工厂流水线经过 $1,2,\dots,N$ 的 $N$ 个步骤，才算完成。

对于每个步骤 $i$，都有两种处理该步骤的机器 $S_i$ 和 $T_i$ 可供购买：

• 机器 $S_i$：每台可处理 $A_i$ 个产品，每台价格为 $P_i$ 日元。

• 机器 $T_i$：每台可处理 $B_i$ 个产品，每台价格为 $Q_i$ 日元。

在每个步骤中，两种机器可以购买任意数量（包括零台）。

假设步骤 $i$ 在引入机器后，可以处理 $W_i$ 个需要经过步骤 $i$ 的产品，我们把这个 $W_i$ 定义为步骤 $i$ 的处理量。

同时将工厂流水线的处理能力定义为所有步骤的处理量中的最小值，即 $\displaystyle\ \min^{N}_{i=1}\ W_i$。

现在问在总预算为 $X$ 日元的情况下，工厂流水线可达到的最大处理能力是多少。

输入格式

第一行输入两个整数 $N,X$ 。

接下来 $N$ 行，每行输入四个整数 $A_i,P_i,B_i,Q_i$ 。

输出格式

输出一个整数，表示工厂流水线可达到的最大处理能力。

样例

输入输出样例 #1

输入 #1

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

输出 #1

4

例如，通过以下方式引入机器，可以将处理能力提高到 $4$，这是可达到的最大值：

• 为步骤 $1$ 引入 $2$ 台机器 $S_1$。

  • 相当于在该步骤一次可以处理 $4$ 个产品，总成本为 $10$ 日元。

• 为步骤 $2$ 引入 $1$ 台机器 $S_2$ ， 引入 $1$ 台机器 $T_2$。

  • 相当于在该步骤一次可以处理 $1+3=4$ 个产品，总成本为 $1+3=4$ 日元。

• 为步骤 $3$ 引入 $2$ 台机器 $T_3$。

  • 相当于在该步骤一次可以处理 $4$ 个产品，总成本为 $8$ 日元。

输入输出样例 #2

输入 #2

1 10000000
100 1 100 1

输出 #2

1000000000

输入输出样例 #3

输入 #3

1 1
1 10000000 1 10000000

输出 #3

0

有时可能总费用不购买任何一台机器，导致无法获得正的处理能力。

输入输出样例 #4

输入 #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

输出 #4

894742

数据范围

• 所有输入均为整数。

• $1\ \le\ N\ \le\ 100$

• $1\ \le\ A_i,B_i\ \le\ 100$

• $1\ \le\ P_i,Q_i,X\ \le\ 10^7$

大样例下载