C. Colored Tree
time limit per test
1.5 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

A colored weighted tree is a tree where each vertex $$$i$$$ has weight $$$w_i$$$ and color $$$c_i$$$. A "good" set of a colored weighted tree is any subset of the tree's vertices that satisfies the following conditions:

  • no two vertices in the subset are connected by an edge,
  • all vertices in the subset have different colors.

The weight of a "good" set is defined as the sum of the weights of the vertices in this set (an empty set has a weight of $$$0$$$).

Given a colored weighted tree, find the maximum weight of a "good" set in it.

Input

The first line contains two integers, $$$n$$$ ($$$1 \le n \le 1000$$$) and $$$C$$$ ($$$1 \le C \le 10$$$): the number of vertices in the tree and the number of different colors, respectively.

The second and third lines contain $$$n$$$ integers each: $$$w_1, w_2, \ldots, w_n$$$ ($$$1 \le w_i \le 10^{9}$$$) and $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le C$$$): the weights of the vertices and their colors, respectively.

The next $$$n - 1$$$ lines describe the edges of the tree. The $$$j$$$-th of these lines contains two integers $$$u_j$$$ and $$$v_j$$$ ($$$1 \le u_j, v_j \le n$$$, $$$u_j \neq v_j$$$): the numbers of the vertices connected by the $$$j$$$-th edge. It is guaranteed that the given graph is a tree.

Output

Output a single integer: the maximum possible weight of a "good" set in the given tree.

Examples
Input
4 4
1 1 1 1
1 2 3 4
1 2
1 3
1 4
Output
3
Input
5 3
5 1 2 3 1
1 2 2 3 1
1 2
1 3
2 4
2 5
Output
8