传感器优化困境 2

题目描述

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

对于每道工序 $i$，有 $S_i$ 和 $T_i$ 两种可购置的机器：

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

每种机器可以购买任意数量（也可以为 $0$）。

设引入机器后，工序 $i$ 每天能够处理 $W_i$ 个产品。

这里，生产能力定义为 $W$ 的最小值，即 $\displaystyle \min^{N}_{i=1} W_i$。

在总预算 $X$ 日元内，求能够达到的最大生产能力。

输入格式

输入按以下格式从标准输入给出：

$N$ $X$
$A_1$ $P_1$ $B_1$ $Q_1$
$A_2$ $P_2$ $B_2$ $Q_2$
$\vdots$
$A_N$ $P_N$ $B_N$ $Q_N$

输出格式

以整数输出答案。

样例

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

4

例如，按如下方式引入机器，可以达到最大生产能力 $4$。

• 工序 1：引入 2 台机器 $S_1$。每天可处理 $4$ 个产品，总费用 $10$ 日元。
• 工序 2：引入 1 台机器 $S_2$。每天可处理 $1$ 个产品，总费用 $1$ 日元。
• 工序 2：引入 1 台机器 $T_2$。每天可处理 $3$ 个产品，总费用 $3$ 日元。
• 工序 3：引入 2 台机器 $T_3$。每天可处理 $4$ 个产品，总费用 $8$ 日元。

1 10000000
100 1 100 1

1000000000

1 1
1 10000000 1 10000000

0

也可能存在无法达到正生产能力的情况。

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$