Lisa phục vụ bàn trong một nhà hàng. Tối nay là sinh nhật của cô ta nên cô ta đề nghị đầu bếp chuẩn bị món ăn đặc biệt cho các bạn của cô. Món ăn đặc biệt của đầu bếp được làm từ N nguyên liệu khác nhau. Để làm một suất ăn mỗi loại nguyên liệu cần một số lượng nhất định. Có một vài nguyên liệu đã sẵn có trong bếp và Lisa phải mua các nguyên liệu còn lại tại một cửa hàng gần đó. Cửa hàng này bán tất cả các nguyên liệu cần thiết, mỗi nguyên liệu có 2 loại gói nhỏ và gói lớn. Lisa có M USD và muốn mua hàng sao cho đầu bếp có thể làm được nhiều suất ăn nhất.

Dữ liệu: Vào từ file văn bản DINER.INP

• Dòng đầu tiên ghi hai số nguyên N, M (1 ≤N ≤ 100, 1 ≤ M ≤ 100000)
• N dòng tiếp theo, mỗi dòng ghi 6 số nguyên là thông tin về một loại nguyên liệu. Các thông tin này, theo thứ tự, là:
  • X, 10 ≤X ≤ 100 là lượng nguyên liệu cần dùng cho 1 suất ăn
  • Y, 1 ≤ Y ≤ 100 là lượng nguyên liệu có ở trong bếp
  • SM, 1 ≤ SM ≤ 100 là kích cỡ của gói nhỏ
  • PM, 10 ≤ PM ≤ 100 là giá của gói nhỏ
  • SV, SM < SV ≤ 100 là kích cỡ của gói lớn
  • PV, PM < PV ≤ 100 là giá của gói lớn

Kết quả: Ghi ra file văn bản DINER.OUT

Một số nguyên duy nhất là số lượng suất ăn mà đầu bếp có thể làm cho Lisa.

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

2 100
10 8 10 10 13 11
12 20 6 10 17 24

Output

5

Giải thích ví dụ

• Ví dụ 1: Trong ví dụ trên, với 99 USB Lisa mua 3 gói nhỏ và 1 gói lớn của nguyên liệu thứ 1, mua 1 gói nhỏ và 2 gói lớn của nguyên liệu thứ hai. Đầu bếp có 51 đơn vị nguyên liệu 1 và 60 đơn vị của nguyên liệu 2 để làm 5 suất ăn