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
  • S_M, 1≤S_M≤100 là kích cỡ của gói nhỏ
  • P_M, 10≤P_M≤100 là giá của gói nhỏ
  • S_V, S_M<S_V≤100 là kích cỡ của gói lớn
  • P_V, P_M<P_V≤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.