AT_abc374_e.[ABC374E] Sensor Optimization Dilemma 2

某产品的制造需要经过 $1,2,\dots,N$ 编号的 $N$ 个工序。

对于每个工序 $i$，有两种可以购买的机器 $S_i,T_i$：

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

每种机器都可以购买 $0$ 台或多台。

假设通过购买机器后，第 $i$ 个工序每天可以处理 $W_i$ 个产品。
此时，定义制造能力为 $W$ 的最小值，即 $\min_{i=1}^{N} 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$

请输出一个整数，表示答案。

限制条件

• 输入均为整数。
• $1 \le N \le 100$
• $1 \le A_i,B_i \le 100$
• $1 \le P_i,Q_i,X \le 10^7$

样例解释 1

例如，按如下方式购买机器，可以使制造能力达到 $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$ 元。

样例解释 3

也有可能无法获得正的制造能力。

由 ChatGPT 4.1 翻译