Sau chuyến đi đầu tiên trong phần \(1\), PhuocThien cùng DatthicTech, KimHieu, conghieupt2555 và vov đã mang về được rất nhiều món đồ kỷ niệm từ các điểm dừng chân trên hành trình 30/4. Có món là một chiếc huy hiệu nhỏ, có món là một bức ảnh chụp vội bên đường, có món là một mảnh giấy ghi chú do cả nhóm trao nhau trên xe, và cũng có món là những vật phẩm đặc biệt chỉ xuất hiện ở đúng một nhánh của chuyến đi. Ban đầu, PhuocThien nghĩ chỉ cần gom tất cả vào một chiếc túi duy nhất là xong, nhưng rất nhanh anh nhận ra chiếc túi này không hề đơn giản như tưởng tượng: mỗi vật phẩm đều có trọng lượng, giá trị riêng, và còn thuộc về một nhóm hành trình khác nhau. Nếu sắp xếp không khéo, chiếc túi sẽ bị lấp đầy bởi những món đồ nặng nhưng không thật sự hữu ích, khiến giá trị kỷ niệm cuối cùng thấp hơn rất nhiều so với tiềm năng thật sự của chuyến đi.

DatthicTech là người đầu tiên nêu ý kiến rằng chỉ cần chọn những món đồ có giá trị lớn nhất trước là được, nhưng KimHieu phản bác ngay lập tức. Trong những tình huống như thế này, món đồ tốt nhất không phải lúc nào cũng là món có giá trị lớn nhất, mà là món giúp mở ra nhiều lựa chọn hơn cho phần còn lại của túi. Một món vật phẩm nhẹ hơn có thể cho phép mang thêm hai món khác, và đôi khi tổng giá trị cuối cùng lại vượt xa một món đồ rất đắt nhưng chiếm quá nhiều chỗ. vov thì nhận xét rằng đây chính là kiểu bài toán không thể giải bằng cảm tính, vì số phương án tăng quá nhanh khi số lượng vật phẩm lớn dần. Nếu kiểm tra từng tập con, chuyến đi sẽ kết thúc trước khi lời giải xuất hiện.

Nhìn lại toàn bộ chiến lợi phẩm của chuyến đi, PhuocThien phát hiện ra một quy luật quan trọng: các vật phẩm không chỉ có trọng lượng và giá trị, mà còn được gắn với một mã nhóm \(c_i\). Mọi vật phẩm có cùng mã nhóm đều thuộc cùng một cụm hành trình, tức là chúng được tạo ra từ cùng một đoạn đường hoặc cùng một kỷ niệm đặc biệt. Điều này khiến bài toán không còn là chiếc túi bình thường nữa, mà trở thành một bài toán quy hoạch động có cấu trúc nhóm. Mỗi nhóm có thể gồm nhiều vật phẩm, và việc chọn trong một nhóm sẽ ảnh hưởng trực tiếp đến khả năng chọn ở các nhóm khác vì tổng sức chứa của túi là hữu hạn. PhuocThien hiểu rằng nếu không xử lý theo đúng thứ tự, anh sẽ bị mắc kẹt trong hàng loạt phương án trùng lặp và không thể tìm ra lời giải tối ưu.

conghieupt2555 đề nghị rằng nên ghép các vật phẩm theo nhóm rồi xử lý lần lượt từng nhóm như những khối độc lập, còn DatthicTech cho rằng nên thử mọi khả năng trong từng nhóm trước rồi mới đưa vào trạng thái chung của chiếc túi. Sau một thời gian bàn bạc, cả nhóm thống nhất rằng đây chính là dạng bài kinh điển của quy hoạch động cái túi, nhưng có thêm một tầng nhóm đặc biệt: Trong mỗi nhóm hành trình, bạn chỉ được phép chọn tối đa một vật phẩm để mang theo, không được kết hợp nhiều vật phẩm từ cùng một nhóm vào túi. Mỗi lần ghép một nhóm mới, các trạng thái cũ phải được giữ lại cẩn thận, vì có thể phương án tốt nhất ở nhóm sau lại phụ thuộc vào việc nhóm trước đã dùng bao nhiêu dung lượng.

Điều làm bài toán này trở nên thú vị là ở chỗ nó không chỉ kiểm tra khả năng tối ưu hóa, mà còn kiểm tra khả năng tổ chức thông tin. KimHieu nói rằng nếu xem mỗi nhóm hành trình như một câu chuyện nhỏ, thì nhiệm vụ của người giải là phải biết chọn những câu chuyện nào đáng để đưa vào chiếc túi sao cho tổng giá trị cảm xúc cao nhất. Có những nhóm chỉ có một vật phẩm rất mạnh, có những nhóm lại có nhiều vật phẩm nhỏ nhưng ghép với nhau thì cực kỳ hiệu quả, và có những nhóm gần như chỉ để "đánh lạc hướng" người giải bằng các phương án tưởng đẹp nhưng lại không tối ưu. vov thì nhắc rằng một lời giải tốt phải vừa đúng, vừa gọn, vừa đủ nhanh để xử lý toàn bộ dữ liệu trong giới hạn cho phép.

Nhiệm vụ của bạn là thay PhuocThien hoàn thiện chiếc túi đặc biệt ấy. Hãy chọn một tập vật phẩm sao cho tổng trọng lượng không vượt quá giới hạn của túi \(W\), đồng thời thỏa mãn quy tắc nhóm hành trình: từ mỗi nhóm, bạn chỉ được chọn tối đa một vật phẩm duy nhất (hoặc không chọn vật phẩm nào từ nhóm đó). Việc xét chọn phải được thực hiện theo đúng cấu trúc nhóm để tối đa hóa tổng giá trị kỷ niệm. Mục tiêu cuối cùng là tối đa hóa tổng giá trị của các vật phẩm đã chọn. Nếu có nhiều cách chọn cho cùng một giá trị lớn nhất, chỉ cần in ra giá trị đó.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, W\) \((1 \le n \le 2000,\ 1 \le W \le 10^5)\).
• \(n\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(w_i, v_i, c_i\) trong đó:
• \(w_i\) là trọng lượng của vật phẩm thứ \(i\),
• \(v_i\) là giá trị của vật phẩm thứ \(i\),
• \(c_i\) là mã nhóm hành trình của vật phẩm thứ \(i\).
• Hai vật phẩm có cùng mã \(c_i\) thuộc cùng một nhóm.

Output

In ra một số nguyên duy nhất là tổng giá trị lớn nhất có thể đạt được mà không vượt quá sức chứa \(W\).

Ràng buộc

• \(1 \le n \le 2000\).
• \(1 \le W \le 10^5\).
• \(1 \le w_i \le W\).
• \(1 \le v_i \le 10^9\).
• \(1 \le c_i \le n\).

Example

5 10
3 6 1
4 7 1
5 9 2
2 4 2
6 10 3

17

Scoring

• Subtask \(1\) (\(50\%\) điểm): \(n \le 200\), \(W \le 2000\).
• Subtask \(2\) (\(50\%\) điểm): Không có ràng buộc thêm.