Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#00020E

Cook

Lisa is working like a waitress in a restaurant. This evening she is celebrating its birthday so she has asked cook to prepare for her and her friends his favorite meal. Cook's favorite meal consists N ingredients.

To prepare one portion of that meal he needs a certain amount of each ingredient. He has some amount of ingredients in his kitchen and the rest will Lisa buy.

In a store, Lisa can find all ingredients she needs, but she only have K money and she wants to spend money in that way so cook can make the most portion he can make with that amount of ingredients.


InputIn the first line of standard input there are two natural numbers: N and K, 1 ≤ N ≤ 100, 1 ≤ K ≤ 100 000.

In every of next N lines there are 6 natural numbers:

• X, 10 ≤ X ≤ 100, amount of ingredients needed for a portion of cooks meal in grams,
• Y, 1 ≤ Y ≤ 100, amount of ingredients that are already available in the kitchen, in grams,
• SM, 1 ≤ SM < 100, the size of a small pack of ingredients in grams,
• CM, 10 ≤ CM < 100, price of a small pack of ingredient,
• SV, SM < SV ≤ 100, the size of a big pack of ingredients in grams,
• CV, CM < CV ≤ 100, price of a big pack of ingredient.

OutputIn the first and only line of standard output print the largest possible number of portions that cook can prepare, if Lisa smart spends the money which is available.

Input:
2 100
10 8 10 10 13 11
12 20 6 10 17 24
Output:
5

Input:
3 65
10 5 7 10 13 14
10 5 8 11 14 15
10 5 9 12 15 16
Output:
2

Explanation of first example:

Lisa will for 99 amount of money buy: 3 small and 1 big pack of first ingredient, 1 small and 2 big packs of second ingredient (3*10 + 1*11 + 1*10 + 2*24 = 99). Cook will then have 51 grams of first ingredient and 60 grams of second ingredient which is enough for 5 portions of cooks favorite meal.



Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.