AT_arc107_f [ARC107F] Sum of Abs

有一个包含 $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 \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 翻译