Nhặt vàng và liệt kê

Một người thợ kim hoàn tới hầm mỏ có \(N\) viên quặng vàng. Viên quặng thứ \(i\) có giá trị \(a_i\) và chiếm thể tích \(b_i\). Chiếc balô của anh có sức chứa tổng cộng là \(M\). Mỗi viên chỉ được mang tối đa một lần.

Hãy chọn một số viên quặng sao cho tổng thể tích không vượt quá \(M\) và tổng giá trị là lớn nhất. Ngoài giá trị lớn nhất, cần in ra cả cách chọn cụ thể.

Vì có thể có nhiều cách chọn tối ưu, ta quy ước chỉ chấp nhận đúng một cách như sau: biểu diễn cách chọn bằng dãy nhị phân \(x_1 x_2 \dots x_N\) (\(x_i = 1\) nếu viên \(i\) được chọn, ngược lại \(x_i = 0\)). Trong tất cả các cách chọn cho tổng giá trị lớn nhất, hãy in cách chọn có dãy \(x_1 x_2 \dots x_N\) lớn nhất theo thứ tự từ điển (nghĩa là ưu tiên chọn viên có chỉ số nhỏ hơn).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(M\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\): giá trị và thể tích của viên quặng thứ \(i\).

Output

• Dòng đầu: số \(k\) là số viên quặng được chọn.
• Dòng thứ hai: \(k\) chỉ số của các viên được chọn, theo thứ tự tăng dần, cách nhau bởi dấu cách (nếu \(k = 0\) thì in một dòng trống).

Constraints

• \(1 \le N \le 1000\)
• \(1 \le M \le 1000\)
• \(0 \le a_i \le 10^5\)
• \(0 \le b_i \le 10^5\)

Sample Input 1

5 8
6 3
5 4
9 5
4 2
0 3

Sample Output 1

2
1 3

Sample Input 2

3 5
4 2
4 2
0 1

Sample Output 2

3
1 2 3

Explanation

Ở ví dụ 1, giá trị lớn nhất là \(15\) đạt bằng viên \(\{1, 3\}\) (thể tích \(8\)); viên \(\{1,2,4\}\) có tổng thể tích \(9\) vượt quá \(M\) nên không hợp lệ. Ở ví dụ 2, giá trị lớn nhất là \(8\) bằng cách chọn hai viên đầu; thêm viên 3 (giá trị \(0\)) vẫn còn đủ chỗ (tổng thể tích \(5\)) và cho dãy nhị phân \(111\) lớn hơn \(110\) theo từ điển nên được chọn.