[ARC107F] Sum of Abs

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

[problemUrl]: https://atcoder.jp/contests/arc107/tasks/arc107_f $ 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 $

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

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 与えられるグラフは連結とは限りません．