Cây khế nhà Khánh rất sai quả nên có một con chim to to đến ăn. Ăn xong, chim chở Khánh ra đảo để trả công bằng các viên đá quý. Đảo có \(N\) viên đá quý, mỗi viên đá quý có trọng lượng, giá trị và số lượng riêng. Cậu ấy muốn chuyển hết tất cả N viên đá quý của mình về nhà. Nhưng khổ nỗi những viên đá quý này lại có trọng lượng và kích thước khổng lồ. Khánh may gấp rút một cái túi ba trăm gang to đùng nhưng vẫn chưa chắc chứa hết đống đá quý này. Khổ quá đi! Lấy viên nào, bỏ viên nào bây giờ! Các bạn hãy giúp cậu ấy tìm ra một cách chọn đá quý để thu được giá trị lớn nhất và đương nhiên cái túi không bị rách.

Yêu cầu: Hãy chọn các viên đá sao cho tổng giá trị lớn nhất mà túi không bị rách?

Input

• Dòng 1: Hai số nguyên: Số viên đá quý \(N\ (1 \le 𝑁 \le 100)\) và sức chứa của cái túi \(M\ (1 \le 𝑀 \le 10000)\).
• \(N\) dòng tiếp theo: Mỗi dòng ghi 3 số nguyên: Khối lượng \(W_i\), giá trị \(V_i\) và số lượng \(A_i\) của viên đá thứ \(i\) (\(1\le 𝑊_𝑖, 𝑉_𝑖, 𝐴_𝑖 \le 1000\)).

Output

• Một số nguyên duy nhất là giá trị lớn nhất tìm được.

Example

3 4 
1 4 2 
2 7 2 
3 6 1   

15