Имеется дерево из $n$ вершин, где вершина номер $i~(1 \le i \le n)$ имеет $c_i$ монет. Вам следует выбрать такое подмножество вершин, в котором никакие две из них не являются соседними (то есть вершины соединенные ребром), а сумма монет в выбранных вершинах наибольшая. \includegraphics{https://static.e-olymp.com/content/90/90bb1bf5eda77c35998a37c2faea86c23525dcfb.gif} \InputFile Первая строка содержит количество вершин $n~(1 \le n \le 10^5)$ в дереве. Каждая из следующих $n - 1$ строк содержит два числа $u$ и $v~(1 \le u, v \le n)$, задающих ребро в дереве. Последняя строка содержит $n$ целых неотрицательных чисел $c_1, ... c_n$ --- количество монет в вершинах дерева. \OutputFile Вывести максимально возможную сумму монет в выбранном подмножестве вершин дерева.