Довгі дерева

Обмеження: 3 сек., 512 МіБ

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

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

Вхідні дані

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

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

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

Вихідні дані

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

Обмеження

$3 \le n \le 3000$,

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

$|a_i| \le 10^9$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 10 -3 2 7 2 5 10 1 2 2 3 2 4 2 5 7 5 6 5	26

Примітки

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

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