Một sự thật ít người biết về Bessie và những người bạn là chúng rất thích thi leo cầu thang. Một sự thật được biết đến rộng rãi hơn là bò thực sự không thích đi xuống cầu thang. Vì vậy, sau khi đàn bò đua xong lên đỉnh tòa nhà chọc trời yêu thích, chúng gặp phải một vấn đề. Từ chối đi cầu thang xuống, đàn bò buộc phải dùng thang máy để trở về tầng trệt.

Thang máy có tải trọng tối đa là \(W\) pound (\(1 \le W \le 100\,000\,000\)), và con bò \(i\) nặng \(C_i\) pound (\(1 \le C_i \le W\)). Hãy giúp Bessie tìm cách đưa tất cả \(N\) con bò (\(1 \le N \le 18\)) xuống tầng trệt bằng số chuyến thang máy ít nhất. Tổng khối lượng của những con bò trong mỗi chuyến thang máy không được lớn hơn \(W\).

Dữ liệu vào

• Dòng 1 chứa \(N\) và \(W\), cách nhau bởi một dấu cách.
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa số nguyên \(C_i\), cho biết khối lượng của một con bò.

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất \(R\), biểu thị số chuyến thang máy tối thiểu cần thiết.
• Các dòng từ 2 đến \(1+R\): Mỗi dòng mô tả tập hợp những con bò đi trong một trong \(R\) chuyến thang máy xuống dưới. Mỗi dòng bắt đầu bằng một số nguyên cho biết số bò trong tập hợp, tiếp theo là chỉ số của từng con bò trong tập hợp đó.

Ví dụ

4 10
5
6
3
7

3
2 1 3
1 2
1 4

Nguồn

USACO 2012 March Contest, Gold Division — Cows in a Skyscraper

Tác giả: Mark Gordon, Neal Wu, Fatih Gelgi, 2012.