Опыт

Компания X имеет N сотрудников, организованных в строгую иерархическую структуру в виде дерева. На вершине этой структуры находится генеральный директор (CEO), который имеет номер 1. У него есть подчиненные, у которых, в свою очередь, также могут быть подчиненные, и так далее, до рядовых сотрудников, у которых нет подчиненных. Все сотрудники пронумерованы от 1 до N. У каждого сотрудника есть определенный опыт, обозначаемый неотрицательным целым числом W[i] для i-го сотрудника.

Компания планирует распределить сотрудников по группам для выполнения различных проектов. При этом необходимо соблюсти следующие условия:

• Каждая группа должна включать как минимум одного человека, и каждый сотрудник должен входить ровно в одну группу.

• Группа может состоять только из сотрудников, которые являются последовательными подчиненными друг друга. То есть, если группа включает сотрудников j[1], j[2], j[3], ..., то j[2] должен быть непосредственным подчиненным j[1], j[3] – непосредственным подчиненным j[2], и так далее.

После завершения проекта общий опыт группы увеличивается на Wmax - Wmin, где Wmax – максимальный опыт, а Wmin – минимальный опыт среди членов группы. Задача компании – максимизировать суммарный прирост опыта всех групп.

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

Входные данные

Первая строка содержит одно целое число N – количество сотрудников в компании (1 ≤ N ≤ 10^5).

Вторая строка содержит N неотрицательных целых чисел W[1], W[2], ..., W[N], представляющих опыт каждого сотрудника (0 ≤ W[i] ≤ 10^9).

Следующие N-1 строк содержат по два целых числа u и v, обозначающих, что сотрудник с номером v является непосредственным подчиненным сотрудника с номером u.

Выходные данные

Выведите одно целое число – максимальный общий прирост опыта для компании.

Пример

Одна из конфигураций, которая максимизирует прирост опыта, это {1, 5, 3}, {6, 2, 4}, {7}. Другая возможная конфигурация с тем же приростом – {1, 5}, {3}, {6, 2, 4}, {7}.

Примеры