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.

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$

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

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.