You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的简单无向图。对于 $i=1,2,\ldots,M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。另外，对于 $i=1,2,\ldots,N$，顶点 $i$ 被分配了一个正整数 $W_i$，并且在顶点 $i$ 上放置了 $A_i$ 个棋子。

只要图上还存在棋子，就不断重复以下操作：

• 首先，从图上的棋子中选择一个并将其移除，设该棋子原本所在的顶点为 $x$。
• 从与 $x$ 相邻的若干个顶点（可以为空）组成的集合 $S$ 中选择一个，要求 $\sum_{y\in S} W_y < W_x$，然后在 $S$ 中的每个顶点各放置 $1$ 个棋子。

请输出可以进行操作的最大次数。

另外，可以证明无论如何操作，经过有限次操作后，最终图上不会剩下棋子。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
$W_1$ $W_2$ $\ldots$ $W_N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

6 6
1 2
2 3
3 1
3 4
1 5
5 6
9 2 3 1 4 4
1 0 0 0 0 1

输出 #1

5

输入输出样例 #2

输入 #2

2 1
1 2
1 2
0 0

输出 #2

0

输入输出样例 #3

输入 #3

10 20
4 8
1 10
1 7
5 9
9 10
8 10
7 5
1 4
7 3
8 7
2 8
5 8
4 2
5 1
7 2
8 3
3 4
8 9
7 10
2 3
25 5 1 1 16 5 98 3 21 1
35 39 32 11 35 37 14 29 36 1

输出 #3

1380

说明/提示

限制条件

• 所有输入的值均为整数。
• $2 \leq N \leq 5000$
• $1 \leq M \leq \min\{N(N-1)/2, 5000\}$
• $1 \leq u_i, v_i \leq N$
• $u_i \neq v_i$
• $i \neq j \implies \{u_i, v_i\} \neq \{u_j, v_j\}$
• $1 \leq W_i \leq 5000$
• $0 \leq A_i \leq 10^9$

样例解释 1

在下述说明中，各顶点上的棋子数量用数列 $A=(A_1, A_2, \ldots, A_N)$ 表示。初始时，$A=(1,0,0,0,0,1)$。考虑按照以下步骤进行操作：

• 从顶点 $1$ 移除一个棋子，并在顶点 $2,3$ 各放置一个棋子。此时 $A=(0,1,1,0,0,1)$。
• 从顶点 $2$ 移除一个棋子。此时 $A=(0,0,1,0,0,1)$。
• 从顶点 $6$ 移除一个棋子。此时 $A=(0,0,1,0,0,0)$。
• 从顶点 $3$ 移除一个棋子，并在顶点 $2$ 放置一个棋子。此时 $A=(0,1,0,0,0,0)$。
• 从顶点 $2$ 移除一个棋子。此时 $A=(0,0,0,0,0,0)$。

上述操作共进行了 $5$ 次，这是可以进行操作次数的最大值。

样例解释 2

在本输入样例中，初始时图上没有任何棋子。

由 ChatGPT 4.1 翻译