BALO 1

Trong một cửa hàng có n món hàng khác nhau. Món hàng thứ i có trọng lượng là w_i và có giá trị là v_i. Một tên trộm đột nhập vào cửa hàng đó và hắn mang theo một cái túi có thể chịu được trọng lượng tối đa là m. Tên trộm đó phải lấy những món hàng nào để cái túi không bị rách mà vẫn mang lấy được tổng giá trị là lớn nhất? Được biết mỗi món hàng chỉ có duy nhất một món.

Dữ liệu vào:

- Dòng đầu tiên gồm hai số nguyên n, m cách nhau một khoảng cách (1 ≤ n, m ≤ 1000).

-  n dòng tiếp theo, dòng thứ i ghi cặp số nguyên w_i và v_i. (1 ≤ w_i, v_i≤ 10000).

Dữ liệu ra:

-     Dòng đầu tiên là một số duy nhất là tổng giá trị lớn nhất mà tên trộm lấy được.

-     Dòng thứ hai là những vật mà tên trộm đó đã lấy theo thứ tự tăng dần.

Ví dụ: