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

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\). Для всіх інших вершин це значення є меншим.

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