Problem Description

To cook a certain dish, you need $n$ kinds of ingredients. For the $i$-th ingredient, one dish requires $a_i$ units, and the kitchen currently has $b_i$ units. For each ingredient, you can buy more from the supermarket. There are two package types: small and large. For the $i$-th ingredient, a small package contains $sm_i$ units and costs $pm_i$ yuan per package; a large package contains $sv_i$ units and costs $pv_i$ yuan per package. For each ingredient, you may buy any number (possibly zero) of small and large packages.

You have $m$ yuan. Find the maximum number of dishes you can cook with this money.

Input Format

The first line contains two integers: the number of ingredients $n$ and the amount of money $m$.

Lines $2$ to $(n + 1)$ each contain six integers. Line $(i + 1)$ contains $a_i, b_i, sm_i, pm_i, sv_i, pv_i$, with meanings as described in the Description.

Output Format

Output one integer in a single line, the maximum number of dishes you can cook.

2 100
10 8 10 10 13 11
12 20 6 10 17 24

5

3 65
10 5 7 10 13 14
10 5 8 11 14 15
10 5 9 12 15 16

2

Hint

Constraints

For all testdata, it is guaranteed that:

• $1 \leq n \leq 100$, $1 \leq m \leq 10^5$.
• $10 \leq a_i \leq 100$, $1 \leq b_i \leq 100$.
• $1 \leq sm_i \lt sv_i \leq 100$, $1 \leq pm_i \lt pv_i \leq 100$.

Notes

This problem is translated from COCI2007-2008 Regional Competition T3 KUHAR。

Translated by ChatGPT 5