MKUHAR  Most Servings Meal
English  Vietnamese 
Lisa works as a waitress in a restaurant. Tonight is her birthday so Lisa asked the chef to prepare his special meal for her friends. The chef's meal is made of N ingredients. To prepare one serving of the meal he needs a certain amount of each ingredient.
There are some ingredients already available in the kitchen and Lisa will buy the rest at the grocery store. The store has all the necessary ingredients, each coming in smaller and larger packages. Lisa has M dollars and wants to spend them so that the chef can make the most servings of his meal.
Input
The first line contains two integers N and M, 1 ≤ N ≤ 100, 1 ≤ M ≤ 100 000. Each of the following N lines contains 6 positive integers, information about one ingredient. These specify, in order:
• X, 10 ≤ X ≤ 100, the amount of the ingredient needed in one serving;
• Y, 1 ≤ Y ≤ 100, the amount of the ingredient already available in the kitchen;
• SM, 1 ≤ SM < 100, the size of the smaller package at the store;
• PM, 10 ≤ PM < 100, the price of the smaller package;
• SV, SM < SV ≤ 100, the size of the larger package; and
• PV, PM < PV ≤ 100, the price of the larger package.
Output
Output the largest number of servings the chef can make if Lisa spends her money wisely.
Sample
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
In the first example, for 99 dollars Lisa will buy three smaller and one larger package of the first ingredient, as well as one smaller and two larger packages of the second ingredient (3x10 + 1x11 + 1x10 + 2x24 = 99).
The chef will then have 51 units (8 + 3x10 + 1x13) of the first ingredient and 60 units (20 + 1x6 + 2x17) of the second ingredient, enough for 5 servings.
hide comments
kspoj:
20191029 18:04:09
@lovebabber Choose a and b to minimize a * PM + b * PV subject to a * SM + b * SV >= k*xy where k is the number of people you are trying to serve (mid in binary search) Last edit: 20191029 18:05:05 

lovebabbar:
20180606 17:39:25
can you give a hint how to select the packages? 

aloochaat1998:
20160926 17:39:31
For finding no.of smaller packages and larger packages,use simple brute force.Rest is simple binary search. ;) 

Aman Singh:
20160726 11:45:30
^^ Plain cin/ cout will work. 

alpha coder:
20160607 04:39:51
scanf / printf is sufficient ! :) 

Deepak Gupta:
20141221 22:12:58
Fast I/O worked for me. 
Added by:  ~!(*(@*!@^& 
Date:  20090228 
Time limit:  0.167s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO PERL6 
Resource:  COI 08 Region 