Production Line Optimization

Little Ming is remodeling a production line in a factory workshop. The workshop has $n$ machines forming a tree with root node 1. Each machine (node) $i$ has a weight $w_i$. The interpretation of $w_i$ depends on the type of node:

• Leaf nodes: $w_i$ indicates that the machine produces $w_i$ units of raw material per unit time and sends them to its parent.
• Internal nodes (other than the root): $w_i$ indicates the maximum units of raw material that can be processed per unit time and then forwarded to its parent.
• Root node: $w_1$ indicates the maximum number of finished products that can be packaged per unit time.

Due to capacity issues, some nodes receive more raw material than they can process, causing the production line to malfunction. To fix this, Little Ming plans to delete some machines (i.e. nodes) so that, in the remaining tree (which must include the root), each node receives an amount of raw material that does not exceed its capacity.

For any node $v$, let its production (or flow) be defined as follows:

If $v$ is a leaf, its production is $w_v$. For an internal node, if it keeps a subset of its children, then the total inflow is the sum of their productions. However, the node can process at most $w_v$ units. In other words, if we denote the production from node $v$ as $f(v)$, then by choosing a subset $S$ of its children:

[ f(v) = \max\Biggl{w_v, \max_{S \subseteq \text{children}(v),, \sum_{u \in S} f(u) \le w_v} \Bigl(\sum_{u \in S} f(u)\Bigr) \Biggr} ]

Your task is to compute the maximum units of finished products (i.e. $f(1)$) that the root can package per unit time after optimally deleting some nodes.

inputFormat

The first line contains a single integer $n$ ($1 \le n \le 100$), the number of machines.

The second line contains $n$ space-separated integers: $w_1, w_2, \ldots, w_n$, where $w_i$ is the weight (capacity or production) of the $i$-th machine.

The following $n-1$ lines each contain two integers $u$ and $v$, indicating there is an edge from node $u$ (the parent) to node $v$ (the child), thus forming a tree rooted at 1.

outputFormat

Output a single integer: the maximum number of finished products that can be packaged per unit time at the root after optimally deleting some nodes.

sample

3
5 3 4
1 2
1 3

5