問題文

A 社のサーバーは $1, 2, ..., N$ の番号がついた $N$ 個のデバイスを $N - 1$ 本のケーブルで接続した構造をしています。 $i$ 本目のケーブルはデバイス $U_i$ とデバイス $V_i$ を接続しています。 どの異なる $2$ つのデバイスも何本かのケーブルを介して接続されています。

各デバイス $v$ ($1 \\leq v \\leq N$) には $0$ でない整数 $A_v$ が割り当てられています。 これらの整数は以下のことを表します。

• $A_v < 0$ のとき、デバイス $v$ はコンピュータであり、大きさ $\-A_v$ の電力を消費することを表す。
• $A_v > 0$ のとき、デバイス $v$ はバッテリーであり、大きさ $A_v$ の電力を供給できることを表す。

あなたは何本か ($0$ 本以上) のケーブルを切断することで A 社のサーバーの機能を停止させることにしました。 ケーブルを切断するとデバイスはいくつかの連結成分に分かれます。 これら連結成分がすべて以下のいずれかの条件を満たすようになれば、サーバーは機能を停止します。

• 連結成分に属する各デバイス $v$ に対する $A_v$ の値がすべて正である。すなわち、連結成分にコンピュータが存在しない。
• 連結成分に属する各デバイス $v$ に対する $A_v$ の値の和が負である。すなわち、連結成分における電力供給が不足している。

サーバーの機能を停止させるためには、最小で何本のケーブルを切断すれば良いでしょうか。

制約

• $1 \\leq N \\leq 5,000$
• $1 \\leq |A_i| \\leq 10^9$ ($1 \\leq i \\leq N$)
• $1 \\leq U_i, V_i \\leq N$ ($1 \\leq i \\leq N - 1$)
• $U_i \\neq V_i$ ($1 \\leq i \\leq N - 1$)
• どの異なる $2$ つのデバイスも何本かのケーブルを介して接続されている。
• 入力値はすべて整数である。

---

入力

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $...$ $A_N$ $U_1$ $V_1$ $U_2$ $V_2$ $:$ $U_{N - 1}$ $V_{N - 1}$

出力

答えを出力せよ。

---

入力例 1

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

出力例 1

1

デバイス $1$ とデバイス $2$ を結ぶケーブルを切断すればよいです。

---

入力例 2

4
1 2 3 4
1 2
1 3
1 4

出力例 2

0

---

入力例 3

6
10 -1 10 -1 10 -1
1 2
2 3
3 4
4 5
5 6

出力例 3

5

---

入力例 4

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

出力例 4

3

---

入力例 5

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

出力例 5

3