User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

33.3% (1/3)

Description

波路特石是一名剛畢業的新鮮人,他想要應徵一些工作,他在網站上看到的工作有些會需要參加過一些實習課才能去做,每一個實習課可能是免費的或是需要花錢才能參加,而且去工作能領到的錢說不定小於他參加實習課所花的錢,因此他決定要計算出他要去哪些公司工作才能賺最多的錢,當然要去工作的話需要先上過那些公司指定的實習課,範例如下:

有三家公司 $A,B,C$ 其需要參加的實習課及工作後能領到的報酬如下:
$A:b$ ,能領 $5$ 元
$B:a,d$ ,能領 $3$ 元
$C:a,c$ ,能領 $7$ 元

實習課價格如下:
$a:2$ 元
$b:4$ 元
$c:3$ 元
$d:5$ 元

則最好的方案是去 $A$ 與 $C$ 工作,而為了要去工作,需要參加 $a,b,c$ 的實習課,因此賺到的錢為 $(5+7)-(2+4+3)=3$ 。

以上例子中 $A$ 代表第一個工作, $B$ 代表第二個工作;
而 $a$ 代表第一個實習課, $b$ 代表第二個實習課。
以此類推,為了讓讀者更清楚題意才使用英文代號。
在以下輸入中的工作及實習課代號均為正整數,範例輸入一即為上面的例子。

當然波路特石是聰明人,如果做什麼工作都沒辦法賺錢的話,他會在家陪伴老婆,也就是不會有賠錢的情況發生。

Input Format

第一行有兩個正整數 $N,M$ ,分別代表能應徵的工作數量與實習課數量。
第二行有 $N$ 個非負整數,第 $i$ 個非負整數 $s_i$ 代表做第 $i$ 個工作能得到的報酬。
第三行有 $M$ 個非負整數,第 $i$ 個非負整數 $b_i$ 代表要參加第 $i$ 個實習課所需的花費。
接下來 $N$ 行,每行第一個數字 $k_i$ ,代表第 $i$ 個工作需要參加的實習課數量,接下來有 $k_i$ 個正整數,代表要應徵工作前要參加的實習課代號 $a_{ij}$ ,這 $k_i$ 個數字由小到大排序且不會有重複的。

  • $1\leq N,M\leq2000$
  • $0\leq s_i,b_i\leq10^ 4$
  • $0\leq k_i\leq M$
  • $1\leq a_{ij} \leq M$
  • $\sum\limits_{i=1}^ {n}k_{i}\leq 2000$

Output Format

請輸出波路特石最多能賺到多少錢。

Sample Input 1

本測資即為題目敘述中的例子

3 4
5 3 7
2 4 3 5
1 2
2 1 4
2 1 3

Sample Output 1

本測資即為題目敘述中的例子

3

Sample Input 2

4 3
3 5 2 8
1 4 2
1 2
2 1 2
2 2 3
0

Sample Output 2

11

Sample Input 3

3 3
123 456 789
321 654 987
1 1
1 2
1 3

Sample Output 3

0

Hints


波路特石的老婆
PIXIV:39996290

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~10 $n\leq10$ 10
2 11~16 一個工作至多只需要參加一個實習課 8
3 17~24 不會有任兩個不同工作需要參加同樣的實習課 17
4 0~33 無特別限制 65

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 4
1 1000 65536 65536 1 4
2 1000 65536 65536 1 4
3 1000 65536 65536 1 4
4 1000 65536 65536 1 4
5 1000 65536 65536 1 4
6 1000 65536 65536 1 4
7 1000 65536 65536 1 4
8 1000 65536 65536 1 4
9 1000 65536 65536 1 4
10 1000 65536 65536 1 4
11 1000 65536 65536 2 4
12 1000 65536 65536 2 4
13 1000 65536 65536 2 4
14 1000 65536 65536 2 4
15 1000 65536 65536 2 4
16 1000 65536 65536 2 4
17 1000 65536 65536 3 4
18 1000 65536 65536 3 4
19 1000 65536 65536 3 4
20 1000 65536 65536 3 4
21 1000 65536 65536 3 4
22 1000 65536 65536 3 4
23 1000 65536 65536 3 4
24 1000 65536 65536 3 4
25 1000 65536 65536 4
26 1000 65536 65536 4
27 1000 65536 65536 4
28 1000 65536 65536 4
29 1000 65536 65536 4
30 1000 65536 65536 4
31 1000 65536 65536 4
32 1000 65536 65536 4
33 1000 65536 65536 4