Trong siêu thị có ~n~ đồ vật ~(N≤1000)~, đồ vật thứ ~i~ có trọng lượng là ~W[i]≤1000~ và giá trị V[i] ≤1000. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng ~M (M≤1000)~. Hỏi tên trộm sẽ lấy đi những đồ vật nào để được tổng giá trị lớn nhất. Giải quyết bài toán trong trường hợp mỗi vật chỉ được chọn một lần.

Dữ liệu vào: Dòng 1: ~N, M~ cách nhau ít nhất một dấu cách

• ~N~ dòng tiếp theo: Mỗi dòng gồm 2 số ~W_i, V_i~, là chi phí và giá trị đồ vật thứ ~i~.

Kết quả ra: Ghi giá trị lớn nhất tên trộm có thể lấy.

Ví dụ:

Input:

5 13
3 4
4 5
5 6
2 3
1 1

Output:

16 4
1
2
3
5