← 返回题目列表

AtCoder · abc374_e

H. 传感器优化困境 2

中文机器翻译题面 查看原题

分数: 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