配点: 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
有时不进入任何房子是最优的选择。