分数: 475 点
问题陈述
某种产品的制造需要 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 日元,找出可实现的最大生产能力。
约束
- 所有输入值均为整数。
- 1 \le N \le 100
- 1 \le A_i,B_i \le 100
- 1 \le P_i,Q_i,X \le 10^7
输入
输入由标准输入按以下格式给出:
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
3 22 2 5 3 6 1 1 3 3 1 3 2 4
示例输出 1
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 日元。
示例输入 2
1 10000000 100 1 100 1
示例输出 2
1000000000
示例输入 3
1 1 1 10000000 1 10000000
示例输出 3
0
可能存在无法实现正产能的情况。
示例输入 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