In the country Treeland there are n cities and $n - 1$ bidirectional roads. Each road connects some pair of cities and from any city you can get to any other one using only the given roads. City 1 is the root of the tree. There is a value $a{_i}$ associated with each city i. For any city i, there exists a set $S{_i}$ which contains the distinct values of all cities j such that j lies in sub-tree rooted at city i and it's distance from city i is divisible by magic number m. Hence no element of set $S{_i}$ repeats. Strength of city i is the number of elements in above defined set $S{_i}$ whose value is strictly less than $a{_i}$. Find $\sum a{_i}*x{_i}‎$ where $x{_i}$ is Strength of city i.

Input Format

First line contains two integers n - number of cities and m - magic number. Next $n - 1$ line contains two integers u and v denoting edge between city u and city v. Next line contains n integers - where each integer $a{_i}$ is value of city i.

Output Format

Print single integer which is answer of the problem - $\sum a{_i}*x{_i}‎$.

Input Constraints

• 1 <= n <= $10^5$

• 1 <= m <= $13$

• 1 <= $u, v$ <= n

• 1 <= $a{_i}$ <= $10^6$

Setter : Tanmay Patel