Є дерево із $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 Виведіть максимально можливу суму монет у вибраній підмножині вершин дерева.