Разноцветным взвешенным деревом называется дерево, у которого у каждой вершины $$$i$$$ есть вес $$$w_i$$$ и цвет $$$c_i$$$. «Хорошим» множеством разноцветного взвешенного дерева является любое подмножество вершин дерева, которое удовлетворяет следующим условиям:
Определим вес «хорошего» множества как суммарный вес вершин в этом множестве (пустое множество имеет вес $$$0$$$).
Дано разноцветное взвешенное дерево, необходимо найти максимальный вес «хорошего» множества в нём.
Первая строка содержит два целых числа $$$n$$$ ($$$1 \le n \le 1000$$$) и $$$C$$$ ($$$1 \le C \le 10$$$) — количество вершин в дереве и количество различных цветов, соответственно.
Вторая и третья строки содержат по $$$n$$$ целых чисел $$$w_1, w_2, \ldots, w_n$$$ ($$$1 \le w_i \le 10^{9}$$$) и $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le C$$$) — веса вершин и их цвет, соответственно.
Следующие $$$n - 1$$$ строк описывают рёбра дерева. В $$$j$$$-й из этих строк содержится два целых числа $$$u_j$$$ и $$$v_j$$$ ($$$1 \le u_j, v_j \le n$$$, $$$u_j \neq v_j$$$) — номера вершин, соединённых $$$j$$$-м ребром. Гарантируется, что заданный граф является деревом.
Выведите одно число — наибольший возможный вес «хорошего» множества в данном дереве.
4 41 1 1 11 2 3 41 21 31 4
3
5 35 1 2 3 11 2 2 3 11 21 32 42 5
8
