Problem

You are given a binary tree consisting of N nodes. Every node contains an integer value (which may be negative).

A route is any sequence of connected nodes. The route may start and end at any two nodes, but each node can appear at most once.

The value of a route is the sum of the values of all nodes on it.

Find the maximum possible route value.

Input

N value1 left1 right1 value2 left2 right2 ... valueN leftN rightN

• lefti and righti denote the left and right child of node i.
• -1 indicates that the child does not exist.

Node 1 is the root.

Output

Print the maximum route sum.

Constraints

• 1 ≤ N ≤ 3 × 10^5
• -10^9 ≤ value[i] ≤ 10^9