pA 的袋鼠在無限次跳躍後來到一個盛產豬腳的城市，這個城市有 \(n\) 間超商和 \(n-1\) 條道路，每條道路連接兩間超商，且都可以雙向通行，並且保證任兩間超商之間可以經過有限條道路到達。此外，在第 \(i\) 座超商，總共有 \(w_i\) 隻豬腳。現在，袋鼠將從超商1出發去購買豬腳。當袋鼠在某一間超商時，她可以選擇要購買多少豬腳，因為袋鼠很想要吃豬腳，所以她只會選擇買下超商的所有豬腳或是完全不買。並且，袋鼠為了避免迷路，不會經過同一間超商兩次。最後，袋鼠希望自己每一次購買豬腳的數量都大於前一次購買豬腳的數量(第一次除外)。現在袋鼠想問問你，她最多可以在幾間超商購買豬腳呢?

Input

第 \(1\) 行有一個正整數 \(n\) 代表超商數量， \(1 \leq n \leq 2\times 10^5\)

第 \(2\) 行到第 \(n\) 行，每行有兩個正整數 \(u,v\) ，代表超商 \(u\) 和 \(v\) 之間有一條道路， \(1 \leq u,v \leq n\)

第 \(n+1\) 行有 \(n\) 個整數，第 \(i\) 個正整數代表 \(w_i\) ，意義如題序所述， \(\forall 1 \leq i \leq n, 1 \leq w_i \leq 10^9\)

Output

輸出一個正整數，代表袋鼠最多可以在幾間超商購買豬腳

Constraints

第 \(1\) 組測資， \(\forall (u,v),v=u+1\) 。 (\(20 \%\))

第 \(2\) 組測資， \(\forall (u,v),u=1\) 。 (\(10 \%\))

第 \(3\) 組測資， \(n \leq 5000\) 。 (\(30 \%\))

第 \(4\) 組測資，無特別限制。 (\(40 \%\))

Sample Input 1

6
1 2
4 3
2 5
1 3
6 2
9 5 1 2 1 9

Sample Output 1

2

Sample Input 2

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

Sample Output 2

3

Sample Input 3

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

Sample Output 3

2

Sample Input 4

1
1

Sample Output 4

1