Đan là người thắng cuộc trong một kì thi lập trình và được nhận các phần thưởng theo cách sau: Ban tổ chức chuẩn bị n món quà, các món quà được đánh số từ \(1\) đến \(n\), món quà thứ \(i\) \((1 \leq i \leq n)\) có khối lượng \(w_{i}\) với giá trị \(v_{i}\) và cho phép Đan chọn lấy một số món quà nhưng tổng khối lượng các món quà không được vượt quá \(S\). Đan mong muốn chọn các món quà thỏa mãn yêu cầu của Ban tổ chức mà tổng giá trị là lớn nhất. Tuy nhiên, điều này rất khó để thực hiện tối ưu. Do đó, khi chọn các món quà xong, Ban tổ chức cho Đan thêm một cơ hội, Đan có thể lập trình để tìm một phương án bỏ chọn một món quà và thay bằng một món quà chưa chọn khác mà tổng khối lượng tất cả các món quà chọn vẫn không vượt quá \(S\). Tất nhiên, Đan cũng có quyền không đổi, giữ nguyên các món quà đã chọn.

Yêu cầu: Cho thông tin các món quà và phương án mà Đan đã chọn, hãy tính tổng giá trị lớn nhất có thể đạt được.

Input

• Dòng đầu chứa hai số nguyên dương \(n, S\) \((S \leq 10^{9})\)
• Dòng thứ \(i\) \((1 \leq i \leq n)\) trong \(n\) dòng tiếp theo chứa hai số nguyên dương \(w_{i}, v_{i}, c_{i}\) (\(w_{i},v_{i} \leq 10^{9}\); \(c_{i}\) bằng \(1\) hoặc \(0\) tương ứng món quà thứ \(i\) được chọn hoặc không được chọn trong phương án chọn trước khi được phép đổi chọn một món quà).

Dữ liệu đảm bảo tổng khối lượng các món quà mà Đan đã chọn không vượt quá \(S\).

Output

• In ra chuẩn một dòng chứa một số nguyên là tổng giá trị lớn nhất có thể đạt được.

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{5}\).

Example

5 13
2 5 0
3 6 1
4 7 1
5 8 1
6 9 0

22

3 10
4 5 1
6 8 1
5 7 0

13