CS218 KNAPSACKSẮP XẾP VA LY 0-1 Cho va li có thể chứa W đơn vị trọng lượng. Có N đồ vật, đồ vật thứ i có trọng lượng A[i] và giá trị C[i]. Hãy sắp xếp các đồ vật vào trong va li để tổng giá trị va li là lớn nhất. Dữ liệu vào: Dòng thứ nhất chứa hai số nguyên N và W N dòng tiếp theo, mỗi dòng chứa hai số nguyên tương ứng với A[i] và C[i] (i=1n)

Dữ liệu ra: Dòng thứ nhất ghi tổng giá trị lớn nhất của các vật được chọn Các dòng tiếp theo, mỗi dòng ghi 3 số, tương ứng với số hiệu, trọng lượng và giá trị của vật được chọn.

Ví dụ: INPUT 3 10 1 70 5 300 5 300

OUTPUT 600 2 5 300 3 5 300