Giải bài trực tuyến

Lisa tổ chức sinh nhật và nấu ăn để mời mọi người. Món ăn này cần N loại thực phẩm khác nhau, một số thực phẩm có sẵn trong bếp , còn lại phải mua thêm ở cửa hàng. Cửa hàng bán theo gói lớn và bé và Lisa có M $$$ để mua hàng.

Input

Dòng đầu gồm hai số N và M, 1 ≤ N ≤ 100, 1 ≤ M ≤ 100 000. N dòng sau đó chứa 6 số nguyên mỗi dòng

• X, 10 ≤ X ≤ 100, lượng thực phẩm cần cho 1 xuất
• Y, 1 ≤ Y ≤ 100, số lượng có sẵn trong bếp.
• SM, 1 ≤ SM < 100, kích thước gói loại bé ở cửa hàng.
• PM, 10 ≤ PM < 100, giá gói loại bé.
• SV, SM < SV ≤ 100, kích thước gói loại lớn ở cửa hàng.
• PV, PM < PV ≤ 100, giá gói loại lớn.

Output

Ghi ra số xuất ăn lớn nhất mà Lisa có thể có được với M tiền (ứng với số khách mà Lisa có thể mời được).

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

------------ Tự dịch nốt.

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.