题目描述

$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$ の総和の絶対値である．

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

输入格式

入力は以下の形式で標準入力から与えられる．

$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$

输出格式

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

题目大意

$N$ 个点 $M$ 条边的无向图，每个点有两个权值 $A_i$ 和 $B_i$。可以用 $A_i$ 的代价删除第 $i$ 个节点。并删除与这个点相连的边。一个极大连通块的权值定义为 $B_i$ 的权值和的绝对值。

删除一些节点后，收益定义为所有极大连通块权值之和减去代价和。求最大的可能收益。

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

1

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

2306209

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

4

提示

制約

• $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$
• グラフは自己ループや多重辺を含まない．
• 入力はすべて整数である．

Sample Explanation 1

頂点 $2$ を消すと，コストが $1$ かかります． このとき，グラフは $2$ つの連結成分に分かれます． 頂点 $1$ からなる連結成分のスコアは $|0|=0$ で，頂点 $3,4$ からなる連結成分のスコアは $|-3+1|=2$ です． よって利得は $0+2-1=1$ になります． 利得を $1$ より大きくすることはできないので，$1$ が答えです．

Sample Explanation 3

与えられるグラフは連結とは限りません．