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 có 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 ghi 2 số nguyên dương \(n\) và \(M\). \((1 \leq n,\ M \leq 5000)\)

+ \(n\) dòng tiếp theo mỗi dòng ghi 2 số nguyên dương mô tả một đồ vật có trọng lượng \(x\) và giá trị \(y\) \((1 \leq x \leq M,\ 1 \leq y \leq 10000)\)

Kết quả: một số nguyên dương là tổng giá trị lớn nhất đạt được.

Ví dụ: