User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

28.6% (2/7)

Description

在一個國家中,會有許許多多的企業,
每個企業都會各司其職,負責不同的事務,
而且有些企業因為產業鏈相近的關係,
如果在同一個廠區的話會有經濟效益上的加成。

但是現在因為政府的施政規劃,
所以想將這些企業分配到兩個廠區,
但又希望可以找到一個方法,
使得在分完後的總經濟效益最高,
也就是要求出一個總經濟效益最高的分配方式,
並計算其獲得之總經濟效益為多少。

而總經濟效益的計算方式如下:
令 $Con(a,b)=r$ 表示當 $a$ 與 $b$ 在同一廠區時,貢獻 $r$ 單位的經濟效益;
假設:

  • $Con(A,B)=4$
  • $Con(A,C)=5$
  • $Con(B,C)=3$
  • $Con(B,D)=4$
  • $Con(D,E)=6$

則最好的策略是將 $A,B,C$ 分配在同一個廠區,$D,E$ 在另一個廠區,
這樣獲得的總經濟效益為第一個廠區的 $Con(A,B)+Con(A,C)+Con(B,C)$,
加上第二個廠區的 $Con(D,E)$,
總合為 $(4+5+3)+(6)=18$。

但是某些企業因為一些因素,必須要在指定廠區才能作業。
使用上面的例子,假設 $A$ 必須在第一廠區,
$B$ 必須在第二廠區,
則最佳解為 $A,C$ 在第一廠區,其餘的在第二廠區。
總經濟效益為 $15$。

保證兩個廠區都至少會有一間企業必須在該廠區作業。

Input Format

第一行輸入兩個整數 $N,M$,代表企業數量與經濟效益關係數量。
接下來一行,第一個數字 $K_A$ 代表必須在第一個廠區作業的企業數量,接著會有 $K_A$ 個數字 $A_i$ 代表那些企業的編號。
接下來一行,第一個數字 $K_B$ 代表必須在第二個廠區作業的企業數量,接著會有 $K_B$ 個數字 $B_j$ 代表那些企業的編號。
接下來 $M$ 行,每行有三個數字 $a_k,b_k,r_k$,代表 $Con(a_k,b_k)=r_k$。

  • $1\leq N\leq 300$
  • $1\leq M\leq 1000$
  • $1\leq K_A,K_B\leq N$,$K_A+K_B\leq N$
  • $1\leq A_i,B_j\leq N$,$A_i\neq B_j,\ \forall\,i\ \text{and}\ j$
  • $\forall\,x\neq y,\ A_x\neq A_y$
  • $\forall\,x\neq y,\ B_x\neq B_y$
  • $1\leq a_k,b_k\leq N$,$a_k\neq b_k$
  • $0\leq r_k\leq 10^6$

Output Format

請輸出一個數字,代表在最好的分配方法下,最多可以獲得多少的總經濟效益。

Sample Input 1

5 5
1 1
1 2
1 2 4
1 3 5
2 3 3
2 4 4
4 5 6

Sample Output 1

15

Sample Input 2

8 12
3 5 4 1
2 6 8
6 8 7
6 4 13
2 4 8
7 3 8
3 8 10
4 7 3
6 2 7
2 1 6
2 5 12
1 5 1
8 1 3
2 8 8

Sample Output 2

52

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~22 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1
18 1000 65536 65536 1
19 1000 65536 65536 1
20 1000 65536 65536 1
21 1000 65536 65536 1
22 1000 65536 65536 1