Cây khế

Xem PDF

Nộp bài


Điểm: 15 (thành phần)
Thời gian: 0.4s
Bộ nhớ: 512M

Tác giả:
Dạng bài

Đã 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ố viên đá quý \(N\ (1\leq N\leq100)\) và sức chứa của cái túi \(M\ (1\leq M\leq10000)\);
  • \(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\leq W_i,\ V_i,\ A_i\leq1000)\).

Output

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

Ví dụ

Sample input
3 4 
1 4 2 
2 7 2 
3 6 1
Sample output
15

Ràng buộc

  • Có \(20\%\) test tương ứng với \(20\%\) số điểm của bài có \(N\leq20\);
  • Có \(40\%\) test khác tương ứng với \(20\%\) số điểm của bài có \(Ai\leq100\);
  • \(40\%\) test còn lại không có ràng buộc gì thêm.

Nguồn: anh Nguyễn Xuân Khánh