AT_arc107_f [ARC107F] Sum of Abs
Description
[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 $ の総和の絶対値である.
すぬけくんの**利得**を,$ ( $ スコア $ - $ コストの総和 $ ) $ とします. すぬけくんの利得の最大値を求めてください.
Input Format
N/A
Output Format
N/A
Explanation/Hint
### 制約
- $ 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
与えられるグラフは連結とは限りません.