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

输入 #1

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

输出 #1

4

输入输出样例 #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$

样例解释 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 翻译