29690번 - Ролевая игра 스페셜 저지다국어

문제

Когда у Жени бывает свободное время, он любит тратить его на свою любимую ролевую игру. Конечно же, у него есть мечта --- достичь 255 уровня, то есть набрать необходимое количество очков опыта. К сожалению, у него не так много свободного времени, потому он хочет использовать его максимально эффективно и просит Вас помочь ему в этом.

Набирать очки опыта в игре можно посредством выполнения некоторых заданий. Для каждого задания известно время его выполнения, сколько очков оно приносит и список заданий, которые необходимо выполнить до того, как это задание станет доступно.

Помогите Жене выяснить, какое максимальное количество опыта, он сможет набрать за свободное время.

입력

Первая строка входного файла содержит два целых числа $n$ и $m$ (1ドル \le n \le 16, 1 \le m \le 1000$) --- количество заданий и количество свободного времени у Жени в минутах. В следующих $n$ строках следуют описания заданий по одному в каждой строке в следующем формате: сначала два целых числа $t_i,ドル $p_i$ и $k_i$ (1ドル \le t_i, p_i \le 1000, 0 \le k_i < n$) --- время в минутах, которое занимает выполнение $i$-го задания, сколько опыта получит персонаж Жени при его выполнении, и количество заданий, которые необходимо выполнить до $i$-го, соответственно. Далее следуют $k_i$ различных чисел от 1ドル$ до $n$ --- номера заданий, которые необходимо выполнить до $i$-го.

출력

В первой строке выведите единственное целое число --- максимальное количество опыта, которое Женя может набрать за свободное время. В следующей строке выведите номера заданий, которые необходимо выполнить для получения такого количества опыта, в том порядке, в котором их необходимо выполнять.

제한

힌트