Score : $475$ points

问题陈述

制造某种产品需要$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$日元，找出可实现的最大生产能力。

以上为大语言模型 kimi 翻译，仅供参考。

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