题目描述

给定一个简单无向图，有 $N$ 个顶点和 $M$ 条边。顶点编号为 $1, 2, \ldots, N$，边的编号为 $1, 2, \ldots, M$。在顶点 $i$ ($1 \leq i \leq N$) 上写有两个整数 $A_i$ 和 $B_i$。边 $i$ ($1 \leq i \leq M$) 连接顶点 $U_i$ 和 $V_i$。

Snuke 选择零个或多个顶点删除。删除顶点 $i$ 的代价为 $A_i$。当删除一个顶点时，与该顶点关联的边也会被删除。删除顶点后的 得分 如下计算：

• 得分是所有连通分量得分的总和。
• 连通分量的得分是连通分量中顶点的 $B_i$ 的绝对值之和。

Snuke 的 利润 是得分减去删除顶点的总代价。找出 Snuke 可以获得的最大可能利润。

约束条件

• $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$
• 给定的图中不包含自环或重边。
• 输入中的所有值都是整数。

输入

从标准输入读入输入数据的格式如下：

$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$

输出

输出 Snuke 可以获得的最大可能利润。

示例输入 1

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

示例输出 1

1

删除顶点 $2$ 的代价为 $1$。删除之后，图分为两个连通分量。由顶点 $1$ 组成的连通分量得分为 $|0| = 0$。由顶点 $3$ 和 $4$ 组成的连通分量得分为 $|(-3) + 1| = 2$。因此，Snuke 的利润为 $0 + 2 - 1 = 1$。他无法获得更多利润，因此答案为 $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

示例输出 2

2306209

示例输入 3

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

示例输出 3

4

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