help me pls now

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ố:

• wi là khối lượng của mỗi món bảo vật loại i.
• vi là giá trị của mỗi món bảo vật loại i.
• bi 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ố ai.

Giả sử bạn thu thập pi món bảo vật của loại i, giá trị bạn nhận từ loại i là: pi∗vi−ai∗(pi2)+bi∗[pi>0] Ở đây, biểu thức [pi>0] trả về 1 nếu (pi>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 wi, vi, bi, ai 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

Sample Input 1

Copy1 20 5 20 5 3

Sample Output 1

Copy38

Sample Input 2

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

Sample put 2

11 

làm c++

Bài thu thập kho báu đảm bảo w_i > 0 với mọi i

Subtask 2 bài Thu Thập Kho Báu có n, W <= 3000