Maximum Number of Dishes

You are given n ingredients needed to prepare a dish. To make one dish, you need a_i portions of the i-th ingredient. Currently, you have b_i portions of each ingredient in your kitchen. If additional portions are needed, you can buy them from a supermarket. For each ingredient, the supermarket sells two types of packages:

• A small package contains sm_i portions and costs pm_i money units per package.
• A large package contains sv_i portions and costs pv_i money units per package.

You can buy an arbitrary number (including zero) of each type of package for every ingredient. You have a total of m money units. Determine the maximum number of complete dishes you can prepare.

Note: All formulas are provided in LaTeX format. For each ingredient i and for a candidate number of dishes x, the total required portions are given by:

$$x \times a_i$$

If the kitchen already has b_i portions, the extra portions needed are:

$$R_i = \max(0, x \times a_i - b_i)$$

You must then purchase at least R_i portions using small and large packages. For a fixed number of large packages \(L\) bought for ingredient i, the remaining portions needed are:

$$rem = \max(0, R_i - L \times sv_i)$$

And the number of small packages needed is:

$$S = \left\lceil \frac{rem}{sm_i} \right\rceil$$

The total cost for ingredient i when purchasing \(L\) large packages is:

$$\text{cost}_i = L \times pv_i + S \times pm_i$$

Your task is to choose a number \(x\) (the number of dishes) and decide a purchasing strategy for each ingredient such that the sum of the costs over all ingredients does not exceed m. Find the maximum possible \(x\).

inputFormat

The first line contains two integers n and m, where n is the number of ingredients and m is the total amount of money available.

Then follow n lines, each containing 6 integers:

a_i b_i sm_i pm_i sv_i pv_i

• a_i: Portions of the i-th ingredient required for one dish.
• b_i: Portions of the i-th ingredient already available.
• sm_i and pm_i: Portions per small package and its cost for the i-th ingredient.
• sv_i and pv_i: Portions per large package and its cost for the i-th ingredient.

outputFormat

Output a single integer: the maximum number of dishes that can be prepared with the available money.

sample

1 10
4 2 1 2 3 5

2