分解

题目描述

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

只要图上还有棋子，就重复以下操作：

首先，从图上取走一个棋子，记 $x$ 为放置该棋子的顶点。

选择一个（可能为空的）与 $x$ 相邻的顶点集合 $S$，满足 $\sum_{y \in S} W_y \lt W_x$，并在 $S$ 中的每个顶点上放置一个棋子。

输出最多能执行多少次该操作。

可以证明，无论如何操作，经过有限次迭代后图上都不会再有棋子。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出答案。

样例

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

5

在下面的说明中，用 $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 1
1 2
1 2
0 0

0

该样例输入中，从一开始图上就没有棋子。

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

1380

数据范围

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