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