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 翻译