#2053. KNAPSACK

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Nguồn: Free Contest 7

Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n món hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là M . Vậy kẻ trộm nên bỏ vào ba lô những món nào để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được.

Dữ liệu vào:

  • Dòng đầu tiên chứa hai số nguyên dương n M\ (1 ≤ n, M ≤5000) ;
  • n dòng tiếp theo, mỗi dòng chứa hai số nguyên dương x y mô tả một đồ vật có trọng lượng x và giá trị y\ (1 ≤ x ≤ M, 1 ≤ y ≤10000) .

Dữ liệu ra:

  • In ra tổng giá trị lớn nhất đạt được.

Ví dụ:

Dữ liệu vào:
10 50
33 6
19 3
12 8
22 7
18 3
34 10
14 10
21 9
26 10
40 4
Dữ liệu ra:
27