AT_abc341_f.[ABC341F] Breakdown

给定一个包含 $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$

请输出答案。

限制条件

• 所有输入的值均为整数。
• $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 翻译