Sensor Optimization Dilemma 2

题目描述

某种产品的制造需要 $N$ 个工序，编号为 $1,2,\dots,N$。 对于每个工序 $i$，有两种可购买的机器 $S_i$ 和 $T_i$ 来处理该工序。

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

你可以购买任意数量的每种机器，也可以为零。 假设通过引入机器后，工序 $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

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$例如，通过如下方式引入机器，我们可以实现生产能力 $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$ 日元。
可能存在无法实现正的生产能力的情况。

标签: AtCoder|abc374E

来源

AtCoder|abc374E