Minh họa Balo 0/1
Bạn An chuẩn bị đi dã ngoại với chiếc balo chịu được tối đa W kg. Có n đồ vật, đồ thứ i nặng wi kg và có giá trị vi. Mỗi đồ chỉ lấy tối đa một lần. Hãy chọn đồ sao cho tổng khối lượng không vượt quá W và tổng giá trị lớn nhất.
Dữ liệu vào
Dòng đầu chứa n và W. Mỗi dòng trong n dòng tiếp theo chứa wi và vi.
Kết quả
Tổng giá trị lớn nhất.
Giới hạn
1 ≤ n ≤ 100; 1 ≤ W ≤ 5000; 1 ≤ wi ≤ W; 1 ≤ vi ≤ 10^6.
Ví dụ 1 – vào
4 10 5 10 4 40 6 30 3 50
Ví dụ 1 – ra
90
Ví dụ 2 – vào
2 5 6 100 5 1
Ví dụ 2 – ra
1