Frodo's Increasing Watermelon Feast

Brandy Hall is one of the largest Hobbit-holes, located inside the mighty Buck Mountain. It is the ancestral home of the Brandy Deer family, in which Frodo Baggins' mother comes from. Over centuries, the family expanded Brandy Hall until it filled the entire hill. Each of the n rooms in the hall has exactly one watermelon, and the sweetness of the watermelon in room i is given by a_i.

Every day, Frodo chooses a starting room and an ending room for his journey. Between these two rooms he walks along the unique shortest path in the hall (the rooms are connected by bidirectional circular corridors in such a way that there is exactly one simple path between any two rooms, i.e. the graph forms a tree). In each room along the path (including the start and the end) Frodo may choose to taste the watermelon or ignore it. However, aside from the very first watermelon eaten during the day, every subsequent watermelon he eats must have a strictly greater sweetness than the previous one. In mathematical terms, if the sweetness values of the watermelons Frodo actually eats are x₁, x₂, ..., x_k (in the order he encounters them), then it must be that

x₁ (no restriction), and for each j > 1,
\( x_{j}\gt x_{j-1} \).

Frodo wonders: considering all the choices available to him (which room to start, which room to end, and which watermelons to eat along the unique path between them), what is the maximum number of watermelons he can possibly eat in one day without breaking his rule?

inputFormat

The input starts with an integer n (1 ≤ n ≤ 500) which denotes the number of rooms in Brandy Hall.
Then follow n-1 lines, each containing two integers u and v (1-indexed) indicating that room u and room v are connected by a corridor.

The last line contains n integers a₁, a₂, ... , a_n where a_i represents the sweetness of the watermelon in room i.

outputFormat

Output a single integer: the maximum number of watermelons Frodo can eat in one day without breaking his rule.

sample

3
1 2
2 3
1 2 3

3