MKUHAR - Most Servings Meal

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.



Được gửi lên bởi:~!(*(@*!@^&
Ngày:2009-02-28
Thời gian chạy:0.167s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO PERL6 PYPY RUST SED
Nguồn bài:COI 08 Region

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.