题面翻译

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

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

样例 #1

样例输入 #1

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

样例输出 #1

1

样例 #2

样例输入 #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

样例输入 #3

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

样例输出 #3

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$