Assume we walk along the shortest path from node  to node  in the weighted tree . List the values of passing nodes (including  and ) on the sequence in order, and denote  as the length of Longest Increasing Subsequence for that sequence. Further denote  as:



After removing node  in an unrooted tree , we collect the remaining subtrees as a set and call it .

Denote  as:



Now you are given a weighted tree  with  nodes, you should determine a node  so that the value of  is minimum. In other words, please calculate:

The first line of input contains one integer , indicating the number of nodes.

In the next  lines, there are two integers  in a line, describing the -th edge on the tree.

There are  integers  in the last line,  indicates the value on the node .

Output one integer in a line, indicating .

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

3