롤플레잉 게임

제냐는 여유 시간이 생기면 좋아하는 롤플레잉 게임을 한다. 그의 꿈은 255 레벨에 도달하는 것, 즉 그 레벨에 필요한 경험치를 모으는 것이다. 여유 시간이 많지 않아서 제냐는 그 시간을 최대한 효율적으로 쓰고 싶어 한다. 제냐를 도와주자.

경험치는 과제를 수행해서 얻는다. 각 과제에는 수행하는 데 걸리는 시간, 얻는 경험치, 그리고 그 과제를 시작하기 전에 먼저 수행해야 하는 과제 목록이 있다.

제냐가 여유 시간 동안 얻을 수 있는 경험치의 최댓값을 구하라.

첫 줄에 두 정수 $n$과 $m$ ($1 \le n \le 16$, $1 \le m \le 1000$)이 주어진다. $n$은 과제의 개수, $m$은 제냐의 여유 시간(분)이다. 이어서 $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$ 사이의 과제 번호로 주어진다.

첫 줄에 제냐가 여유 시간 동안 얻을 수 있는 경험치의 최댓값을 한 정수로 출력한다. 둘째 줄에는 그 경험치를 얻기 위해 수행해야 하는 과제의 번호를 수행 순서대로 출력한다.