You are given a tree with n nodes. You are required to color the tree with r colors. Cost of coloring a node with color i is Ai. Also, for each edge, such that the nodes at its end point are colored with the same color i, there is an additional cost of Bi. You are required to find the minimum cost to color all the nodes of the tree.
Input
The first line of the input contains 2 integers n, number of nodes in the tree and r, number of colors.
The second line of the input contains r integers deonting the sequence A.
The third line of the input contains r integers deonting the sequence B.
Each of the next n−1 lines conatins two integers u and v denoting the two nodes which are connected by an edge.
Output
Print one line denoting the minimum cost to color all the nodes in the tree.
Constraints
- 1≤n≤100000
- 1≤r≤1000
- 0≤Ai,Bi≤1000000000
Color vertex 1 with color 2 (cost = 3)
Color vertices 2 & 3 with color 1 (cost = 2 each).
No additional cost because there is no edge such that both its end points are colored with same color.
Total cost = 3 + 2 + 2 = 7.
