题目描述

有一个包含 $N$ 个顶点和 $M$ 条边的简单无向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。每个顶点 $i$（$1 \leq i \leq N$）上写有两个整数 $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$

输出格式

请输出すぬけくん可以获得的最大收益。

样例 1

输入

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

输出

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

输出

2306209

样例 3

输入

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$
• 图中没有自环和重边。
• 所有输入均为整数。

样例解释 1

如果删除顶点 $2$，则需要花费 $1$ 的代价。此时，图被分成两个连通分量。由顶点 $1$ 构成的连通分量得分为 $|0|=0$，由顶点 $3,4$ 构成的连通分量得分为 $|-3+1|=2$。因此收益为 $0+2-1=1$。无法获得比 $1$ 更大的收益，所以答案为 $1$。

样例解释 3

给定的图不一定是连通的。

由 ChatGPT 4.1 翻译