Гільдія злодіїв

Limits: 3 sec., 512 MiB

В одному королівстві є $n$ міст, з’єднаних $n-1$ дорогою так, що між кожною парою міст можливо добратись дорогами. Іншими словами, міста та дороги утворюють дерево.

У кожному місті є банк, в сховищі банку в місті $v$ знаходиться $a_v$ монет. В одному з міст зародилась гільдія злодіїв, яка планує пограбувати банки усього королівства. На жаль, король не знає в якому саме місті це сталось, тож для протидії великого пограбування він вирішив зробити усі дороги королівства односторонніми, попри те, що після цього уже неможливо дістатись з будь-якого міста в будь-яке інше.

Та все ж, пограбування відбудеться! Гільдія пограбує усі банки в усіх містах, в які можливо добратись від міста, де гільдія зародилась.

Король хоче обрати такі напрямки доріг, щоб мінімізувати максимальний можливий збиток. Більш формально, нехай $c_v$ – сума кількості монет у всіх містах, які досяжні з міста $v$ після того, як король обере напрямок кожної дороги (включно з містом $v$). Тоді вам потрібно обрати напрямки так, щоб мінімізувати $\max c_v$.

Input

В першому рядку задано єдине ціле число $n$ – кількість міст королівства.

У наступному рядку задано $n$ цілих чисел $a_i$ – кількість монет у банках.

$i$-ий з наступних $n-1$ рядків містить два цілі числа $u_i$ та $v_i$, що означає, що між містами з цими номерами є дорога.

Output

Виведіть єдине число – мінімальне можливе значення $\max c_v$.

Constraints

$2 \le n \le 10^5$,

$1 \le a_i \le 10^9$,

$1 \le u_i, v_i \le n$.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 1 2 3 4 5 6 7 1 2 1 3 2 4 2 5 4 6 1 7	12

Input (stdin) сopy	Output (stdout) сopy
7 1 1 1 1 1 1 1 1 2 1 3 2 4 2 5 4 6 1 7	3

Input (stdin) сopy	Output (stdout) сopy
2 4 7 1 2	11

Notes

У першому приклад у вершині $v$ знаходиться $v$ монет. Можлива орієнтація ребер зображена на рисунку. Тоді якщо гільдія розташована у вершині 2, а отже вони можуть пограбувати банк у вершинах 1, 2, 4 та 5. $c_2 = a_1 + a_2 + a_4 + a_5 = 12$. Для всіх інших вершин це значення є меншим.

У другому прикладі у кожній вершині по одній монеті. Один з варіантів, як орієнтувати ребра: