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

Kết quả:

• 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ụ:

Input

3 8
3 30
4 50
5 60 

Output

90 

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≤30 ~;
• Có 20% test còn lại tương ứng 20% số điểm với ~ n≤100 ~.