Siêu thị

Trong siêu thị có $n$ gói hàng. Với mỗi $i$ ($1 \le i \le n$), gói hàng thứ $i$ có trọng lượng là $W_i$ ($1 \le W_i \le 100$) và giá trị $V_i$ ($1 \le V_i \le 100$). Chị Hoa vào siêu thị để mua sắm đồ dùng gia đình nhưng sức của chị không thể mang được trọng lượng gói hàng vượt quá $M$ ($1 \le M \le 100$). Hỏi chị Hoa sẽ mua được những gói hàng nào để được tổng giá trị lớn nhất.

Yêu cầu: Em hãy giúp chị Hoa tìm tổng giá trị lớn nhất của các gói hàng được chọn để mang đi.

Từ tệp văn bản MARKET.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương $n$ và $M$;
• $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $W_i$ và $V_i$ (các số cách nhau ít nhất một dấu cách).

Ghi ra tệp văn bản MARKET.OUT gồm một số duy nhất cần tìm. Trường hợp không chọn được gói hàng nào thì ghi kết quả là $-1$.

• Có 80% test tương ứng 80% số điểm với $n \le 30$;
• Có 20% test còn lại tương ứng 20% số điểm với $n \le 100$.