Ректор Уральского государственного университета собирается устроить вечеринку по случаю 80-летия университета. Университет имеет иерархическую структуру сотрудников в виде дерева с корнем в ректоре. Чтобы сделать вечеринку веселой для всех присутствующих, ректор не хочет, чтобы кто-то из ее участников мог столкнуться там со своим непосредственным руководителем (это означает, что сотрудник и его непосредственный руководитель не должны быть одновременно приглашены на вечеринку).

Отдел кадров вычислил уровень праздничного настроения каждого сотрудника университета. Ваша задача – составить список гостей с максимальным суммарным уровнем праздничного настроения, выполнив при этом условие ректора.

В первой строке записано целое число N – количество сотрудников университета (1 ≤ N ≤ 6000). Сотрудники пронумерованы целыми числами в диапазоне от 1 до N. Каждая из последующих N строк содержит рейтинг праздничного настроения соответствующего сотрудника – целое число в диапазоне от −128 до 127. Затем идет описание дерева структуры сотрудников. Каждая строка описания дерева имеет следующую форму

это означает, что K-й сотрудник является непосредственным руководителем L-го сотрудника. Ввод заканчивается строкой

Выведите максимальный суммарный уровень праздничного настроения гостей.