F. Red Blue Tree
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree containing $$$n$$$ nodes where each node is either red node or blue node and the value of the node $$$i$$$ is $$$a_i(1 \le i \le n)$$$.

Let $$$R$$$ be the number of red nodes and $$$B$$$ be the number of blue nodes, then beauty of the tree is defined as ($$$\sum_{i = 1}^R a_i - \sum_{i = 1}^B a_i$$$), i.e., difference between sum of values of all red nodes and sum of values of all blue nodes.

A tree will be called "Perfect Tree" if it satisfies the following conditions :

  • $$$R \gt 0$$$ and $$$B \gt 0$$$.
  • Beauty of the tree $$$\ge 0$$$.

A Forest will be called "Perfect Forest" if atleast one of it's tree is a Perfect tree. Otherwise it will be a "Non-Perfect Forest".

Find the minimum number of edges to remove from the given tree to make the forest "Non-Perfect Forest".

Input

The first line of each test contains single integer $$$n$$$ $$$(1 \le n \le 8000)$$$ — the size of the tree.

The next line contains $$$n$$$ space-seperated integers $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — the value of the $$$i^{th}$$$ node.

The next line contains a binary string $$$S$$$ of length $$$n$$$, where $$$S_i = 0$$$ indicates that $$$i^{th}$$$ node is red node, $$$S_i = 1$$$ indicates that $$$i^{th}$$$ node is blue node.

The next $$$n-1$$$ lines contain two integers $$$x,y$$$ $$$(1 \le x,y \le n, x≠y)$$$ — there is an edge between $$$x$$$ and $$$y$$$.

Output

For each test, print single integer — the minimum number of edges to remove from the given tree to make the forest "Non-Perfect Forest"

Examples
Input
6
2 4 3 6 5 1
011001
5 4
3 1
6 5
1 5
2 3
Output
1
Input
7
9 10 11 5 2 3 6
0010110
3 1
6 4
1 2
3 5
4 7
4 1
Output
2
Note

In the first test, The beauty of the tree is $$$(2+6+5) - (4+3+1) = 5$$$, i.e., beauty $$$\ge 0$$$ and $$$(R = 3 \gt 0)$$$ and $$$(B = 3 \gt 0)$$$. So the given tree is "Perfect tree" and the forest is "Perfect Forest".

After removing the edge between nodes $$$4$$$ and $$$5$$$.

The Beauty of the tree containing nodes {$$$1,2,3,5,6$$$} is $$$(2+5) - (3+4+1) = -1$$$ i.e., beauty $$$ \lt 0$$$. So this tree is "Non-Perfect Tree".

The Beauty of the tree containing nodes {$$$4$$$} is $$$(6) - () = 6$$$ i.e., beauty $$$\ge 0$$$ but $$$(B = 0)$$$. So this tree is "Non-Perfect Tree".

As both trees are "Non-Perfect Tree". The resultant forest is "Non-Perfect Forest". Hence minimum number of edges to remove from the given tree to make the forest "Non-Perfect Forest" is $$$1$$$.