有一种商品的制造需要在工厂流水线经过1,2,...,N 的N 个步骤，才算完成。

对于每个步骤i，都有两种处理该步骤的机器Si和Ti可供购买：

• 机器Si：每台可处理Ai 个产品，每台价格为Pi 日元。
• 机器Ti：每台可处理Bi 个产品，每台价格为Qi 日元。

在每个步骤中，两种机器可以购买任意数量（包括零台）。

假设步骤i在引入机器后，可以处理Wi个需要经过步骤i的产品，我们把这个Wi定义为步骤i的处理量。 同时将工厂流水线的处理能力定义为所有步骤的处理量中的最小值，即 minWi。

现在问在总预算为X日元的情况下，工厂流水线可达到的最大处理能力是多少。

输入以以下格式从标准输入给出：

N X

A1 P1 B1 Q1

A2 P2 B2 Q2

.

.

.

AN PN BN QN

将答案作为整数输出。

所有输入均为整数。 1 ≤ N ≤ 100 1 ≤ Ai,Bi ≤ 100 1 ≤ Pi,Qi,X ≤ 1e7

样例解释1 例如，通过以下方式引入机器，可以将制造能力提高到4，这是可达到的最大值：

• 为工序1引入2台机器S1。- 相当于每天处理4个产品，总成本为10日元。
• 为工序2引入1台机器S2。- 相当于每天处理1个产品，总成本为1日元。
• 为工序2引入1台机器T2。- 相当于每天处理3个产品，总成本为3日元。
• 为工序3引入2台机器T3。- 相当于每天处理4个产品，总成本为8日元。

样例解释3 有时可能无法获得正的制造能力。