F - Sum of Abs Editorial /

Time Limit: 2 sec / Memory Limit: 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_i と V_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.