問題文

頂点に 1 から N の番号がついた N 頂点 N 辺の単純連結無向グラフが与えられます。i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。 各頂点にはいくつかの駒が置かれており、頂点 i には A_i 個の駒が置かれています。

あなたは以下の操作を 0 回以上行うことができます。

• 駒が 1 つ以上置かれている頂点 x と、x に隣接する頂点 y を任意に選ぶ。x に置かれている駒を 1 つ y に移動させる。

あなたの目標は、頂点 i (i = 1, 2, \ldots, N) に駒が B_i 個置かれている状態にすることです。目標の達成に必要な操作回数の最小値を求めてください。

制約

• 3\leq N\leq 3\times 10^5
• 1\leq u_i, v_i \leq N (i = 1, 2, \ldots, N)
• 与えられるグラフは単純かつ連結
• 0\leq A_i, B_i \leq 10^6
• \sum_{i = 1}^N A_i = \sum_{i = 1}^N B_i
• 入力はすべて整数

入力例 1

4
1 2
2 3
3 1
4 3
3 1 3 4
4 2 2 3

出力例 1

3

以下のような順で操作を行うと 3 回の操作で目標を達成できます。

• 頂点 4 の駒を 1 つ頂点 3 に移動させる。
• 頂点 3 の駒を 1 つ頂点 1 に移動させる。
• 頂点 3 の駒を 1 つ頂点 2 に移動させる。

2 回以下の操作では目標を達成できないため、答えは 3 です。

入力例 2

9
1 3
1 9
2 6
8 7
9 2
1 5
8 2
2 3
1 4
9 9 8 2 4 4 3 5 3
3 5 3 4 4 2 8 9 9

出力例 2

29