Кіно#11193

Кіно

2 секунди

128 мегабайтів

Складна

Бессі перебуває в кінотеатрі. Будучи, як завжди, пустотливою, вона вирішила сховатися від фермера Джона протягом $l$ хвилин. Увесь цей час вона хоче безперервно дивитися фільми.

У неї є $n$ фільмів на вибір, кожен з яких має фіксовану тривалість і кілька сеансів протягом дня. Бессі може зайти до кінотеатру та вийти з нього в будь-який момент під час одного з сеансів фільму. Однак вона не може дивитися один і той самий фільм більше одного разу і не може перемкнутися на інший сеанс того самого фільму, якщо цей сеанс перетинається за часом із поточним сеансом, який вона дивиться.

Допоможіть Бессі визначити, чи зможе вона безперервно дивитися фільми з моменту часу $0$ до моменту часу $l$ . Якщо це можливо, визначте мінімальну кількість різних фільмів, які їй необхідно подивитися для досягнення цієї мети (Бессі починає плутатися в сюжетних лініях, якщо дивиться забагато фільмів).

Вхідні дані

У першому рядку містяться два цілих числа, $n (1 \leq n \leq 20)$ n~(1 \le n \le 20) та $l (1 \leq l \leq 1 0^{8})$ l~(1 \le l \le 10^8).

Наступні $n$ рядків описують по одному фільму. Кожен рядок починається з цілого числа, що задає тривалість фільму $d (1 \leq d \leq l)$ d~(1 \le d \le l), та кількості сеансів $c (1 \leq c \leq 1000)$ c~(1 \le c \le 1000). Наступні $c$ цілих чисел у тому самому рядку знаходяться в діапазоні $0 \dots l$ і задають час початку одного з сеансів даного фільму. Часи початку сеансів різні, знаходяться в діапазоні $0 \dots l$ і вказані в порядку зростання.

Вихідні дані

Виведіть одне ціле число — мінімальну кількість фільмів, які Бессі повинна подивитися для досягнення своєї мети. Якщо це неможливо, виведіть $- 1$ .

Приклади

Бессі повинна дивитися перший сеанс четвертого фільму з моменту часу $0$ до моменту часу $20$ . Потім вона дивиться перший сеанс першого фільму з моменту часу $20$ до моменту часу $65$ . Нарешті, вона дивиться останній сеанс другого фільму з моменту часу $65$ до моменту часу $100$ .

Приклад 1