F - Sum of Abs 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 900

問題文

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 を結ぶ辺です.

今から,すぬけくんが 0 個以上の頂点を選んで削除します. 頂点 i を削除するのにかかるコストは A_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 を消すと,コストが 1 かかります. このとき,グラフは 2 つの連結成分に分かれます. 頂点 1 からなる連結成分のスコアは |0|=0 で,頂点 3,4 からなる連結成分のスコアは |-3+1|=2 です. よって利得は 0+2-1=1 になります. 利得を 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.