Cho \(n\) loại đồ vật, loại đồ vật thứ \(i\) có khối lượng \(a_{i}\) và giá trị \(b_{i}\). Hãy chọn các đồ vật bỏ vào ba lô sao cho khối lượng của các đồ vật được chọn không vượt quá \(W\) và giá trị các đồ vật được chọn là lớn nhất. Mỗi đồ vật có số lượng không hạn chế.

Dữ liệu vào:

+ Dòng đầu tiên ghi 2 số nguyên dương \(n\) và \(W\). \((1 \leq n \leq 100,\ 1 \leq W \leq 10000)\)

+ \(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,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ụ: