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 翻译