040 - Get More Money（★7）
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 7 点
問題文
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)
- 入力は全て整数
入力
入力は、以下の形式で与えられます。
N W
A_1 A_2 \cdots A_N
k_1 c_{1,1} c_{1,2} \cdots c_{1,k_1}
k_2 c_{2,1} c_{2,2} \cdots c_{2,k_2}
\vdots
k_N c_{N,1} c_{N,2} \cdots c_{N,k_N}
出力
最終的に得る金額の最大値を、一行に出力してください。
入力例 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
どの家にも入らないのが最適な場合もあります。