003 - Skill Tree

問題

山田君の作ったゲームにはスキルという要素があり、スキルポイントを消費することで新たなスキルを取得することができます。

スキルは$ \ N \ $種類存在し、スキル$ \ 1 \ $は初めから取得済みです。
その他のスキルを取得するにはスキルポイントを消費し、$i \ (2 \leq i \leq N) \ $番目のスキルを取得するにはスキルポイントを$ \ p_i \ $消費します。 また、$k_i \ $種類のスキル$ \ s_{i,1},s_{i,2},\ldots,s_{i,k_i} \ $のうちいずれか$ \ 1 \ $種類以上取得済みである必要があります。

山本君はサービス開始時からこのゲームをプレイしていますが、スキルの存在を知らなかったためスキル$ \ 1 \ $しか取得出来ていません。ただし、スキルポイントは$ \ P \ $ポイント所持しています。
山本君がスキルポイントを消費して取得することのできるスキルの種類数は最大でいくつでしょうか？

入力

入力は以下の形式で標準入力から与えられる

$N \ P$
$p_2 \ k_2 \ s_{2,1} \ s_{2,2} \ldots \ s_{2,k_2}$
$p_3 \ k_3 \ s_{3,1} \ s_{3,2} \ldots \ s_{3,k_3}$
$\vdots$
$p_N \ k_N \ s_{N,1} \ s_{N,2} \ldots \ s_{N,k_N}$

出力

山本君が取得することのできるスキルの種類数の最大値を出力せよ。出力の末尾には改行を入れること。

制約

• $1 \leq N \leq 12$
• $1 \leq P \leq 10^9$
• $1 \leq p_i \leq 10^9$
• $1 \leq k_i \leq N - 1$
• $1 \leq s_{i,j} \leq N$
• $s_{i,j} \neq i$
• $s_{i,j} \neq s_{i,j + 1}$
• 入力は全て整数

入出力例

入力例１

4 5
2 1 1
5 1 1
3 2 2 3

出力例１

3

スキル$ \ 2 \ $を取得してからスキル$ \ 4 \ $を取得することでスキル$ \ 1,2,4 \ $の$ \ 3 \ $つのスキルを取得することができます。
スキルを$ \ 4 \ $つ以上取得することはできないため$ \ 3 \ $が答えとなります。

入力例２

3 10
5 1 3
4 1 2

出力例２

1