It's Mancunian's birthday! His friends will be arriving for the party from all over the country of Neverland. And it goes without saying that they will bring their gifts for Mancunian.

The country of Neverland consists of N cities connected by bidirectional roads. There are exactly \(N-1\) roads and it is possible to travel between any two cities using the roads. Given that there are N cities, there are exactly \(N * (N-1)/2\) distinct unordered pairs of cities. Each such pair corresponds to a path between the two cities. By a huge stroke of coincidence, there are exactly \(N*(N-1)/2\) guests invited to the party. Each of those guests will choose a distinct path and will travel along it.

There are M types of gifts available in the country of Neverland. The \(i^{th}\) such gift (1-indexed) costs i dollars. Each city of the country sells only a single type of gift. While Mancunian's friends are happy for him, they do not want to spend a lot of money on their gift. So, each person will buy the cheapest gift not sold along any city along his/her path.

Can you help Mancunian find out the total value of all the gifts he will receive on his special day?

Input:
The first line contains two integers N and M denoting the number of cities and types of gifts respectively.
The second line contains N integers denoting the types of gifts \(G_{i}\) sold in the cities.
Each of the next \(N-1\) lines consists of two integers, the two endpoints of a road.

Output:
Output a single integer which is the answer to the problem.

Constraints:
\( 3 \le N \le 50000 \)
\( 3 \le M \le 10 \)
\( 1 \le G_{i} < M\)