There is a state (territory) which is a tree rooted at node 1. All the cities (numbered from 1 to \(N+1\)) in this state are connected via bidirectional roads. You have to add toll tax on each road. There are N roads which connect the cities of the state. You have to assign toll taxes on the roads so as to maximize the function Toll described below:

for(i=1;i<=number of cities;i++)
{
    for(j=i+1;j<=number of cities;j++)
    {
        toll+=(toll required to pay to travel from i to j)
     } 
}

You have to maximize the toll tax. Assign the roads by toll taxes from the given array A(using each value exactly once). Find the maximum toll obtained.

Input Format

First line contains N and an integer whose value is always 2.

Then N roads follow containing 2 integers u and v, denoting the cities between which the road is.

Next line contains N space separated values denoting elements of array A.

Output Format

Print the maximum toll which can be obtained.

Input Constraints

\(1 \le N \le 2 * 10^5 \)
\(1 \le A[i] \le 1000\)
\(1 \le u,v \le N+1\)