410208: GYM103984 D Сборы в поход

D. Сборы в походограничение по времени на тест3 секундыограничение по памяти на тест768 мегабайтвводстандартный вводвыводстандартный вывод

Вы собираетесь пойти в поход. Для этого вам нужно разложить всё снаряжение по нескольким рюкзакам. У вас есть неограниченное количество рюкзаков вместительностью $$$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$$$.

Выходные данные

Выведите минимальное количество рюкзаков, которое необходимо, чтобы разместить все вещи по описанным выше правилам.

ПримерВходные данные

3 70
3
10 30 40
2
20 60
1
50

Выходные данные

4

Примечание

Рассмотрим пример из условия. В нём есть вещи трёх типов: наверняка это были укулеле, бутылки с водой и гири.

В первый рюкзак можно положить укулеле объёмом 40 литров и бутылку с водой объёмом 20 литров. Во второй рюкзак можно положить укулеле объёмом 10 литров и бутылку с водой объёмом 60 литров. В третий рюкзак можно положить укулеле объёмом 30 литров. В четвёртом рюкзаке будет лежать гиря объёмом 50 литров. Можно показать, что разложить нужные вещи по трём рюкзакам не получится.