Коровы любят соревноваться в беге по лестницам небоскребов. А вниз потом едут на лифте.
Лифт имеет максимальную вместимость W (1 <= W <= 100,000,000) фунтов, а корова номер i весит Ci (1 <= Ci <= W) фунтов.
Помогите Бесси определить минимальное количество спусков лифта, чтобы переместить вниз все N (1 <= N <= 18) коров.
Сумма весов коров в каждом спуске не должна превышать W.
PROBLEM NAME: skyscraper
Формат входных данных
* Строка 1: N W разделенные одним пробелом
* Строки 2..1+N: Строка i+1 содержит целое число Ci, вес коровы i.
Формат выходных данных
* Строка 1: Минимальное целое, R, указывающее количество требуемых спусков.
* Строки 2..1+R: Каждая строка описывает множество коров, которые были в лифте во время каждого из R спусков. Каждая строка начинается с количества коров в текущем спуске, а затем номера коров через пробел.
Примечание
Мы можем поместить в лифт корову 3 и любую из оставшихся коров. Но все другие коровы не помещаются даже по две. В решении представленном выше, в первом спуске участвуют коровы 1 и 3, Во втором - корова 2, в третьем - корова 4. Существует несколько правильных решений для данного ввода.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 10
5
6
3
7
|
3
|