Є дерево із вершин, де вершина номер має монет. Вам слід обрати таку підмножину вершин, в якій ніякі дві з них не є сусідніми (тобто вершини об’єднані ребром), а сума монет у вибраних вершинах найбільша.
Перший рядок містить кількість вершин в дереві. Кожен з наступних рядків містить два числа і , які задають ребро в дереві. Останній рядок містить цілих невід’ємних чисел — кількість монет у вершинах дерева.
Виведіть максимально можливу суму монет у вибраній підмножині вершин дерева.