Long trees

Limits: 3 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka love trees — connected undirected acyclic graphs. Marichka wrote an integer value \(a_i\) in the \(i\)-th vertex of the tree.

Zenyk also really likes long trees. He considers a tree to be long if its diameter is not less than the number of leaves. Zenyk wants to choose a non-empty connected set of vertices (subgraph) in the given tree that forms a long tree with the maximum sum of vertex values. Help him find this sum.

Input

The first line contains a single integer \(n\) — the number of vertices in the tree. The vertices of the tree are numbered with integers from 1 to \(n\).

The second line contains \(n\) space-separated integers — the values \(a_i\) of the corresponding vertices.

The next \(n-1\) lines describe the edges of the tree as pairs of integers \(u_i\) and \(v_i\), separated by a space.

Output

In a single line, output one integer — the maximum total vertex value of a long tree that is a subgraph of the given one.

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

The diameter of a tree is the length (number of edges) of the longest simple path between a pair of its vertices.

The leaves of a tree are vertices that are directly connected to at most one other vertex in the tree.