Ректор Уральского Государственного Университета решил организовать юбилейный вечер к \textbf{80}-летию основания университета. Университет имеет иерархическую структуру работников, то есть отношения руководителей и подчинённых образуют дерево, в корне которого находится ректор. Сотрудники нумеруются целыми числами в диапазоне от \textbf{1} до \textbf{N}. Отдел кадров предоставил информацию о праздничном настроении каждого сотрудника. Для того, чтобы сделать юбилейный вечер приятным для всех его участников, ректор не хочет, чтобы в нём одновременно принимали участие сотрудник и его непосредственный начальник. Ваша задача составить для ректора список гостей с максимальным праздничным настроением. \InputFile Первая строка содержит количество сотрудников университета \textbf{N} ( \textbf{1} ≤ \textbf{N} ≤ \textbf{6000}). Каждая из последующих \textbf{N} строк содержит праздничное настроение соответствующего сотрудника. Праздничное настроение является целым числом в пределах от \textbf{--128} до \textbf{127}. После этого задано дерево отношений сотрудников и их руководителей. Каждая строка описания дерева имеет вид: \textbf{L K} что означает, что \textbf{K}-ый работник является непосредственным руководителем \textbf{L}-го работника. Входные данные заканчиваются строкой, содержащей два нуля (эта строка не обрабатывается): \textbf{0 0} \OutputFile Вывод должен содержать максимальное суммарное праздничное настроение гостей.