Mô tả và yêu cầu

CHỌN QUÀ

Trong kho của MathX có N món quà, món quà thứ i có trọng lượng Wi và giá trị
Vi. Bạn có một chiếc túi có sức chứa tối đa là M. Hãy chọn các món quà sao cho
tổng trọng lượng không vượt quá M và tổng giá trị là lớn nhất.

Dữ liệu vào

o Dòng 1: Hai số nguyên N,M (1≤N≤1000,1≤M≤1000).
o N dòng tiếp theo: Mỗi dòng gồm 2 số Wi ,Vi (1≤Wi,Vi≤1000).

Kết quả: Một số nguyên duy nhất là tổng giá trị lớn nhất.

Ví dụ

INPUT                          OUTPUT                          GIẢI THÍCH
 3 4                            9                               Chọn quà 1 và 2: 1+2≤4,
 1 4                                                            giá trị 4+5=9
 2 5
 3 1