103744: [Atcoder]ABC374 E - Sensor Optimization Dilemma 2

Problem Statement

The manufacturing of a certain product requires $N$ processes numbered $1,2,\dots,N$.

For each process $i$, there are two types of machines $S_i$ and $T_i$ available for purchase to handle it.

• Machine $S_i$: Can process $A_i$ products per day per unit, and costs $P_i$ yen per unit.
• Machine $T_i$: Can process $B_i$ products per day per unit, and costs $Q_i$ yen per unit.

You can purchase any number of each machine, possibly zero.

Suppose that process $i$ can handle $W_i$ products per day as a result of introducing machines.
Here, we define the production capacity as the minimum of $W$, that is, $\displaystyle \min^{N}_{i=1} W_i$.

Given a total budget of $X$ yen, find the maximum achievable production capacity.

Constraints

• All input values are integers.
• $1 \le N \le 100$
• $1 \le A_i,B_i \le 100$
• $1 \le P_i,Q_i,X \le 10^7$

Input

The input is given from Standard Input in the following format:

$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$

Output

Print the answer as an integer.

Sample Input 1

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

Sample Output 1

4

For example, by introducing machines as follows, we can achieve a production capacity of $4$, which is the maximum possible.

• For process $1$, introduce $2$ units of machine $S_1$.
  • This allows processing $4$ products per day and costs a total of $10$ yen.
• For process $2$, introduce $1$ unit of machine $S_2$.
  • This allows processing $1$ product per day and costs a total of $1$ yen.
• For process $2$, introduce $1$ unit of machine $T_2$.
  • This allows processing $3$ products per day and costs a total of $3$ yen.
• For process $3$, introduce $2$ units of machine $T_3$.
  • This allows processing $4$ products per day and costs a total of $8$ yen.

Sample Input 2

1 10000000
100 1 100 1

Sample Output 2

1000000000

Sample Input 3

1 1
1 10000000 1 10000000

Sample Output 3

0

There may be cases where a positive production capacity cannot be achieved.

Sample Input 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

Sample Output 4

894742

问题陈述

某个产品的生产需要N个过程，编号为1,2,…,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

示例输出