Trong vương quốc Eldoria, có một truyền thuyết về Kho báu của Thời Đại - một kho báu chứa đựng vô số vật phẩm quý giá nằm rải rác khắp vùng đất thần thoại. Những vật phẩm này không chỉ có giá trị riêng biệt, mà còn ẩn chứa những hiệu ứng đặc biệt khi được thu thập với số lượng khác nhau.

Bạn nhận ra có \(N\) loại bảo vật khác nhau, với số lượng bảo vật của mỗi loại là vô hạn. Tuy nhiên, khối lượng bảo vật bạn có thể thu thập không thể vượt quá \(W\).

Người chơi vào vai một nhà thám hiểm tài ba đang trên đường khám phá kho báu này. Tuy nhiên, việc thu thập bảo vật không hề đơn giản. Mỗi loại bảo vật \(i\) có các thông số:

• \(w_i\) là khối lượng của mỗi món bảo vật loại \(i\)
• \(v_i\) là giá trị của mỗi món bảo vật loại \(i\)
• \(b_i\) là giá trị cộng thêm nếu bạn lấy ít nhất một bảo vật loại \(i\)
• Ngoài ra, lấy một loại quá nhiều sẽ khiến cho giá trị của món bảo vật đó hao mòn và giảm đi dựa trên hệ số \(a_i\)

Giả sử bạn thu thập \(p_i\) món bảo vật của loại \(i\), giá trị bạn nhận từ loại \(i\) là:
\(p_i \cdot v_i - a_i \cdot (p_i^2) + b_i \cdot [p_i > 0]\) Ở đây, biểu thức \([p_i > 0]\) trả về 1 nếu \((p_i > 0)\), ngược lại sẽ trả về 0.

Mục tiêu của bạn là thu thập được bộ sưu tập bảo vật có tổng giá trị cao nhất, mà không làm quá tải túi đồ của mình. Hãy tính toán và lựa chọn một cách thông minh để tối ưu hóa phần thưởng trong hành trình này!

Input

• Dòng đầu tiên hai số nguyên dương \(N\) và \(W\) là số loại bảo vật và tổng cân nặng tối đa của các bảo vật bạn có thể thu thập.
• \(N\) dòng tiếp theo, mỗi dòng chứa lần lượt bốn số nguyên \(w_i, v_i, b_i, a_i\) thể hiện các thông số của bảo vật loại \(i\).

Output

• Một số nguyên duy nhất thể hiện giá trị tối đa bạn có thể thu thập từ các món bảo vật mà tổng khối lượng không vượt quá \(W\).

Example

1 20
5 20 5 3

38

3 10
5 6 2 3
2 4 2 1
5 2 3 2

11

Constraints

Trong tất cả các test: \(0 \leq v_i, b_i \leq 10^9, 0 \leq a_i \leq W, 1 \leq w_i \leq 10^9\)

• Subtask 1 (30% số điểm): \(n, W \leq 100\)
• Subtask 2 (30% số điểm): \(a_i = b_i = 0, n, W \leq 3000\) với mọi \(i\)
• Subtask 3 (40% số điểm): \(n, W \leq 3000\)