Problem

You are given a tree consisting of N vertices.

Each vertex contains an integer value, which may be positive, zero, or negative. A path is any sequence of distinct vertices such that every pair of consecutive vertices shares an edge. The path may start and end at any two vertices. The value of a path is the sum of the values of all vertices on that path. Find the maximum possible path value.

Input

N v1 v2 ... vM N-1 lines: ...

Output

Print the maximum path sum.