Giải bài trực tuyến

      Đã hết mùa khế. Trái khế cuối cùng đã rơi và giờ chỉ còn Khánh với cái cây toàn lá là lá. Khánh nhìn cây khế mà tiếc đứt ruột, nước mắt lã chã rơi. Vàng đâu nữa mà xài đây, ơi hỡi! Ngày nọ, con chim to to đó lại đến. Khế đâu ra mà cho nó ăn nữa bây giờ. Nhưng lạ lùng thay, chim to không đòi ăn khế. Số là vợ chim sai chim đi tìm dưa leo cho cô nàng đắp mặt. Chim to ngồi than với Khánh rằng nó đã đi một vòng Trái Đất rồi mà không tìm được trái dưa leo đủ to để đắp vừa khuôn mặt vợ y. Tưởng gì, dưa leo thì Khánh chẳng thiếu vì Khánh ngày nào cũng đắp mặt mà :) Khánh lôi trong tủ lạnh ra một trái dưa leo khổng lồ bự bằng cây dừa đưa cho chim to. Chim to cảm ơn rối rít, rồi lại chở Khánh ra đảo để... vơ vét.

      Lần này, chim to muốn trả ơn Khánh hậu hĩnh hơn nên tặng Khánh một núi đá quý. Có N loại đá quý. Mỗi loại đá lại có trọng lượng, giá trị và số lượng riêng. Rút kinh nghiệm đợt 1, Khánh đã cố may một cái túi bự gấp 10 lần cái túi lần trước mà vẫn không sao cho hết đống đá quý đó vào được. Trái tim Khánh không thể chịu thêm nỗi đau nào quá lớn nữa. Các bạn hãy giúp anh ấy chọn các viên đá cần lấy sao cho anh ấy càng giàu càng tốt và dĩ nhiên là cái túi vẫn không được rách.

Input

• Dòng 1: Hai số nguyên: Số loại đá quý N (1 ≤ N ≤ 100) và sức chứa của cái túi M (1 ≤ M ≤ 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 ≤ W_i, V_i, A_i ≤ 1000).

Output

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

Example

Input:
3 4
1 4 2
2 7 2
3 6 1

Output:
15