問題文

AtCoder 共和国には N 軒の家があり、1 から N までの番号が付けられています。

はじめ、家 i の中には、現金 A_i 円と、k_i 本の鍵（それぞれ家 c_{i,1}, c_{i,2}, \dots, c_{i,k_i} の鍵）が置いてあり、家に入ることでこれらを回収できます。 ただし、任意の j (1 \leq j \leq k_i) に対して c_{i,j} \gt i が保証されます。

また、家 i に入るためには、以下の 2 つのことをする必要があります。

• AtCoder 共和国の中に家 i の鍵があれば、それらをすべて回収した状態にする
• 料金 W 円を支払う

あなたは AtCoder 共和国の家にある現金を集めることで、できるだけ多くの金額を得ようと考えています。家に入る手順をうまく決めたときに、最大で何円得するかを求めてください。 すなわち、家に入って回収した金額を I 円、家に入るために支払った料金を O 円として、I-O の最大値を求めてください。 ただし、家に入るための費用は必要ならいつでも支払えるものとします。

制約

• 2 \leq N \leq 100
• 0 \leq W \leq 10^7
• 0 \leq A_i \leq 10^7
• 0 \leq k_i \leq N-i
• i \lt c_{i,j} \leq N
• c_{i,j} \neq c_{i,k} (j \neq k)
• 入力は全て整数

入力例 1

5 5 5 2 10 3 6 1 3 1 3 0 1 5 0 

出力例 1

2 

家 1,2,3 にこの順で入るのが最適で、5+2+10-3\times 5=2 円得られます。

入力例 2

6 10 8 6 9 1 2 0 1 3 2 3 4 1 5 1 5 1 6 0 

出力例 2

0 

どの家にも入らないのが最適な場合もあります。