1011 - Bài toán cái túi

Time Limit: 1s Memory Limit: 256MB

Submissions: 516 Solved: 86
Description

Một nhà thám hiểm cần đem theo một cái túi có trọng lượng không quá b.
n đồ vật có thể đem theo. Đồ vật thứ j có trọng lượng aj và giá trị sử dụng cj. Hỏi nhà thám hiểm cần đem theo những đồ vật nào để cho tổng giá trị sử dụng là lớn nhất mà tổng trọng lượng đồ vật mang theo cái túi không vượt quá b?
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên dương n,b (n≤ 30, b≤106).
Dòng thứ j trong số n dòng tiếp theo mỗi dòng ghi ra hai số nguyên dương aj,cj≤ 106.
Kết quả:
Ghi ra duy nhất một số là tổng giá trị lớn nhất tìm được của các đồ vật cho vào túi.

Input
Output
Sample Input

    
Sample Output

    
Hint
Source