Trong siêu thị có \(n\) gói hàng. Với mỗi \(i\) \((1 \leq i \leq n)\), gói hàng thứ \(i\) có trọng lượng là \(w_{i}\) \((1 \leq w_{i} \leq 100)\) và giá trị \(v_{i}\ (1 \leq v_{i} \leq 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\ \leq \ m \leq 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.

Dữ liệu vào:

+ 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}\)

Dữ liệu ra:

+ Ghi một số duy nhất là kết quả bài toán. Trường hợp không chọn được gói hàng nào thì ghi kết quả là \(- 1\).

Ví dụ:

Giải thích: Gói hàng thứ 1 và thứ 3 sẽ được chọn để mang đi. Vì chúng có tổng khối lượng không quá 8 và có giá trị lớn nhất là 90.
Ràng buộc:

+ Có 80% test tương ứng 80% số điểm với \(n \leq 30\);

+ Có 20% test còn lại tương ứng 20% số điểm với \(n \leq 100\).