← 返回题目列表

AtCoder · typical90_an

040. 获得更多的钱(★7)

中文机器翻译题面 查看原题

配点: 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

有时不进入任何房子是最优的选择。