問題文

ゅゅさんの学校では，明日に期末テスト当日が迫っています．
テストは $N$ 科目もありますが，ゅゅさんはまだテスト勉強を始めていません．
ゅゅさんのテスト勉強とテストでの得点について，次が成り立ちます．なお，ゅゅさんの学校ではテストに満点が存在せず，各教科には $1$ から $N$ までの番号がついています．

• $i=1,\dots,N$ について，教科 $i$ を勉強すると教科 $i$ で $M$ 点を取れるようになる．
• 教科 $i$ を勉強すると， $k_i$ 個の教科 $A_{ij}\ (1\leq j \leq k_i)$ について深い理解を得やすくなる．
  これにより，教科 $i$ と $A_{ij}$ をどちらも勉強した時，教科 $A_{ij}$ の得点が $B_{ij}$ 点上がる．
• テスト勉強は疲れるので，教科 $i$ を勉強したらもふもふ成分を $C_i$ だけ補充しないといけない．

さて，ゅゅさんはテストで良い成績を取りたいですが，もったいないのでもふもふ成分を補充しすぎたくありません．
適切に勉強する科目を選ぶことで， (テストでの得点の総和) $-$ (補充するもふもふ成分) の値を最大化してください．

入力

$N\ M$
$\mathrm{Info}_1$
$\vdots$
$\mathrm{Info}_N$

ただし，各 $\mathrm{Info}_i$ は次の形式で与えられる．なお， $k_i=0$ の時， $\mathrm{Info}_i$ は $1$ 行のみからなる．

$k_i\ C_i$
$A_{i1}\ \cdots\ A_{ik_{i}}$
$B_{i1}\ \cdots\ B_{ik_{i}}$

• $1 \leq N \leq 100$
• $0 \leq M \leq 10^9$
• $0 \leq k_i \leq N-1\ (1 \leq i \leq N)$
• $1 \leq A_{ij} \leq N,\ A_{ij} \neq i\ (1\leq i \leq N,\ 1 \leq j \leq k_i)$
• $A_{ij} \lt A_{i(j+1)}\ (1\leq i \leq N,\ 1 \leq j \lt k_i)$
• $0 \leq B_{ij},\,C_i \leq 10^9\ (1 \leq i \leq N,\,1 \leq j \leq k_i)$
• 入力は全て整数

出力

ゅゅさんが適切に勉強する科目を選択した時に得られる，(テストでの得点の総和) $-$ (補充するもふもふ成分)の最大値を出力してください．

最後に改行してください．

サンプル

3 100
1 50
2
15
1 200
3
5
2 20
1 2
20 10

150

3 100
1 1000000000
2
15
1 1000000000
3
5
2 1000000000
1 2
20 10

0

3 0
0 5
0 5
0 5

0

5 457570553
2 935681835
3 5
646317136 229179330
1 732053682
5
460010336
3 219961142
2 4 5
805316947 35611550 19086292
2 80909206
3 5
896187710 518478057
2 391491330
3 4
767870553 307252308

4613065789