Задача №114706. Сборы в поход
Вы собираетесь пойти в поход. Для этого вам нужно разложить всё снаряжение по нескольким рюкзакам. У вас есть неограниченное количество рюкзаков вместительностью \(s\) литров каждый.
Всем известно, что когда идёшь в поход, вещи каждого типа нужно брать в нескольких экземплярах, чтобы если одна промокнет, была запасная. Разумеется, разные вещи одного типа нужно класть в разные рюкзаки.
Вы решили взять в поход вещи \(n\) типов, причём вещей типа \(i\) вы решили взять \(k_i\) штук. Каждая вещь имеет свой объем — \(j\)-я вещь типа \(i\) имеет объём \(w_{i, j}\). Вы хотите, используя минимальное число рюкзаков, разложить все имеющиеся вещи по ним так, чтобы суммарный объем вещей в каждом рюкзаке не превышал \(s\), а также чтобы ни в одном из рюкзаков не оказалось двух вещей одного типа. Определите минимальное количество рюкзаков, которое вам понадобится, чтобы пойти в поход.
В первой строке заданы два целых числа \(n\) и \(s\) (\(1 \le n \le 23\), \(1 \le s \le 10^{16}\)) — количество типов предметов и вместительность каждого из рюкзаков.
В следующих \(n\) строках даны описания вещей. В \(i\)-й строке содержится описание вещей \(i\)-го типа. Описание начинается с одного целого числа \(k_i\) (\(1 \leq k_i \leq 23\)) — количества вещей типа \(i\). Затем следуют \(k_i\) целых чисел \(w_{i, j}\) (\(1 \le w_{i, j} \le s\)) — объёмы вещей \(i\)-го типа.
Суммарное количество вещей не превышает \(23\).
Выведите минимальное количество рюкзаков, которое необходимо, чтобы разместить все вещи по описанным выше правилам.
Рассмотрим пример из условия. В нём есть вещи трёх типов: наверняка это были укулеле, бутылки с водой и гири.
В первый рюкзак можно положить укулеле объёмом 40 литров и бутылку с водой объёмом 20 литров. Во второй рюкзак можно положить укулеле объёмом 10 литров и бутылку с водой объёмом 60 литров. В третий рюкзак можно положить укулеле объёмом 30 литров. В четвёртом рюкзаке будет лежать гиря объёмом 50 литров. Можно показать, что разложить нужные вещи по трём рюкзакам не получится.
3 70 3 10 30 40 2 20 60 1 50
4