Довгі дерева

Limits: 3 sec., 512 MiB

Зеник і Марічка полюбляють дерева — зв’язні неорієнтовані ациклічні графи. У \(i\)-й вершині дерева Марічка записала її вартість — ціле число \(a_i\).

Зеник також дуже полюбляє довгі дерева. Він вважає дерево довгим, якщо його діаметр не менший за кількість листків. Зеник хоче вибрати в заданому дереві непусту зв’язну множину вершин (підграф), яка утворює довге дерево з максимальною сумою ваг вершин. Допоможіть йому знайти цю суму.

Input

У першому рядку задано єдине ціле число \(n\) — кількість вершин дерева. Вершини дерева пронумеровані цілими числами від 1 до \(n\).

У другому рядку задано \(n\) цілих чисел через пробіл — вартості \(a_i\) відповідних вершин.

У наступних \(n-1\) рядках задано ребра дерева у вигляді пар цілих чисел \(u_i\) та \(v_i\), розділених пробілом.

Output

У єдиному рядку виведіть одне ціле число — максимальну сумарну вартість вершин довгого дерева, яке є підграфом заданого.

Constraints

\(3 \le n \le 3000\),

\(1 \le u_i, v_i \le n\),

\(|a_i| \le 10^9\).

Samples

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

Notes

Діаметр дерева — це довжина (кількість ребер) найдовшого простого шляху між парою його вершин.

Листки дерева — це вершини, які напряму зв’язані із не більше ніж одною іншою вершиною у дереві.