← 返回题目列表

AtCoder · arc107_f

F. 绝对值总和

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

给定一个简单的无向图 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。 删除顶点时,与该顶点相关的边也会被删除。 的 删除顶点后的 分数 $$$v$$$ 的 计算如下:

  • 分数是所有连接组件的分数之和。
  • 连接分量的分数是以下总和的绝对值 连接组件中顶点的 B_i 。

Snuke 的 利润 is (分数 $$$v$$$ 的) - (成本总和)。 找出 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。 之后,图被分成两个连接的组件。 由Vertex组成的组件的分数 1 is |0| = 0。由顶点组成的组件的分数 3 和 4 is |(-3) + 1| = 2。 因此,Snuke 的利润为 0 + 2 - 1 = 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

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