Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DTTUI2 - Cái túi 2

      Đã 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 Wi, giá trị Vi và số lượng Ai của viên đá thứ i (1 ≤ Wi, Vi, Ai ≤ 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

Được gửi lên bởi:Nguyễn Xuân Khánh
Ngày:2010-01-01
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED

hide comments
2017-08-10 20:30:18
AC = 1 cách rất chi ngu học :v
2016-09-04 05:43:06
To gấp 10 lần thì bác Khánh uống nước thay cơm =))
2015-07-20 20:19:49 there's no salvation for me...
lol code n log *m tối ưu chạy nhanh hơn cả m*n :3 hehehehehehe
2014-11-21 16:59:54 livw
chim to, dưa leo bự

Last edit: 2014-11-21 17:00:11
2014-11-21 16:40:30 bembembem
làm hoài 92.86 ai biết cách sửa sao cho lên k ?
2014-05-30 17:44:03 John and the cows
thanks anh Danh Nguyen :)
2013-06-19 03:34:53 Danh Nguyen
http://petr-mitrichev.blogspot.com/2011/07/integral-bounded-knapsack-problem.html

http://dhruvbird.blogspot.com/2011/09/integer-01-bounded-knapsack-problem.html
2013-02-01 15:38:02 Stupider
may túi to gấp 10 lần
m = 10^9 -> 10^4 :|
2012-11-02 19:24:18 KHD
ưở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

Bác Khánh vui tính thế :)
2011-10-06 13:34:58 hoc, hoc nua...hoc mai
Mình chẳng hiểu nổi chép code để làm gì, làm bài trực tuyến để mình có thể rèn luyện thêm khả năng, học hỏi kinh nghiệm. Mấy bạn chép code làm những bạn khác làm được những bài khó không dám chia sẻ (may be) vì sợ bị chép, làm những người như mình thiệt thòi, nhiều bài quá khó, không làm được thì lại chẳng tìm đâu ra lời giải hix
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.