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.