Có N đồ vật, được đánh số từ 1, 2, … , N. Mỗi đồ vật I ( 1 ≤ I ≤ N) có sức nặng w_i và giá trị v_i. Một người có thể chọn một vài đồ vật trong N đồ vật và bỏ vào trong một cái túi. Sức chứa lớn nhất của túi là W. Hỏi người đó có thể chọn những đồ vật nào để được tổng giá trị lớn nhất?

Ràng buộc:

• 1 ≤ N ≤ 100
• 1 ≤ W ≤ 10⁹
• 1 ≤ w_i ≤ W
• 1 ≤ v_i ≤ 10³