Contest Duration: - (local time) (100 minutes) Back to Home
F - Sum of Abs /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

N 頂点 M 辺の単純無向グラフがあります． 頂点には 1 から N までの，辺には 1 から M までの番号がついています． 各頂点 i (1 \leq i \leq N) には，2 つの整数 A_i,B_i が書かれています． また，辺 i (1 \leq i \leq M) は，頂点 U_iV_i を結ぶ辺です．

• スコアは，各連結成分のスコアの総和である．
• ある連結成分のスコアは，その成分内の頂点の B_i の総和の絶対値である．

すぬけくんの利得を，( スコア - コストの総和 ) とします． すぬけくんの利得の最大値を求めてください．

制約

• 1 \leq N \leq 300
• 1 \leq M \leq 300
• 1 \leq A_i \leq 10^6
• -10^6 \leq B_i \leq 10^6
• 1 \leq U_i,V_i \leq N
• グラフは自己ループや多重辺を含まない．
• 入力はすべて整数である．

入力

N M
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M


出力

すぬけくんの利得の最大値を出力せよ．

入力例 1

4 4
4 1 2 3
0 2 -3 1
1 2
2 3
3 4
4 2


出力例 1

1


入力例 2

10 12
733454 729489 956011 464983 822120 364691 271012 762026 751760 965431
-817837 -880667 -822819 -131079 740891 581865 -191711 -383018 273044 476880
3 1
4 1
6 9
3 8
1 6
10 5
5 6
1 5
4 3
7 1
7 4
10 3


出力例 2

2306209


入力例 3

4 2
1 1 1 1
1 1 -1 -1
1 2
3 4


出力例 3

4


Score : 900 points

Problem Statement

Given is a simple undirected graph with N vertices and M edges. Its vertices are numbered 1, 2, \ldots, N and its edges are numbered 1, 2, \ldots, M. On Vertex i (1 \leq i \leq N) two integers A_i and B_i are written. Edge i (1 \leq i \leq M) connects Vertices U_i and V_i.

Snuke picks zero or more vertices and delete them. Deleting Vertex i costs A_i. When a vertex is deleted, edges that are incident to the vertex are also deleted. The score after deleting vertices is calculated as follows:

• The score is the sum of the scores of all connected components.
• The score of a connected component is the absolute value of the sum of B_i of the vertices in the connected component.

Snuke's profit is (score) - (the sum of costs). Find the maximum possible profit Snuke can gain.

Constraints

• 1 \leq N \leq 300
• 1 \leq M \leq 300
• 1 \leq A_i \leq 10^6
• -10^6 \leq B_i \leq 10^6
• 1 \leq U_i,V_i \leq N
• The given graph does not contain self loops or multiple edges.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M


Output

Print the maximum possible profit Snuke can gain.

Sample Input 1

4 4
4 1 2 3
0 2 -3 1
1 2
2 3
3 4
4 2


Sample Output 1

1


Deleting Vertex 2 costs 1. After that, the graph is separated into two connected components. The score of the component consisting of Vertex 1 is |0| = 0. The score of the component consisting of Vertices 3 and 4 is |(-3) + 1| = 2. Therefore, Snuke's profit is 0 + 2 - 1 = 1. He cannot gain more than 1, so the answer is 1.

Sample Input 2

10 12
733454 729489 956011 464983 822120 364691 271012 762026 751760 965431
-817837 -880667 -822819 -131079 740891 581865 -191711 -383018 273044 476880
3 1
4 1
6 9
3 8
1 6
10 5
5 6
1 5
4 3
7 1
7 4
10 3


Sample Output 2

2306209


Sample Input 3

4 2
1 1 1 1
1 1 -1 -1
1 2
3 4


Sample Output 3

4


The given graph is not necessarily connected.