Có \(n\) món quà, được đánh số từ 1 đến \(n\), món quà thứ \(i\) có khối lượng \(w_i\) và giá trị \(v_i\), và \(c_i=0/1\) tương ứng không chọn/chọn món \(i\). Cần chọn một số món quà sao cho tổng khối lượng của chúng không vượt quá \(S\).

Tuy nhiên, trong số những món không được chọn (có \(c_i=0\)) thì ta được phép đổi một món được chọn (có \(c_j=1\)) với 1 món không được chọn (có \(c_i=0\)), với điều kiện tổng khối lượng các món lấy được không được vượt quá \(S\).

Yêu cầu: Tính tổng giá trị lớn nhất tìm được khi chọn các món quà để có tổng khối lượng không vượt quá \(S\).

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,s(n≤10^5;S≤10^9 ).\)

• Dòng thứ \(i\) 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≤10^9)\) với \(c_i=1/0\) tương ứng món quà thứ \(i\) được chọn hoặc không được chọn.

Dữ liệu đảm bảo tổng khối lượng các món quà mà đã 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.

Ràng buộc

• Subtask 1 (70% số điểm): \(n≤10^3.\)

• Subtask 2 (30% số điểm): \(n≤10^5 \)

Sample Input

3 10
4 5 1
6 8 1
5 7 0

Sample Output

13