Maximum Root-to-Leaf Path Sum in a Binary Tree

You are given a binary tree represented by a list of tuples. Each tuple consists of three elements: the value of a node, the value of its left child, and the value of its right child. A value of 'None' indicates that the corresponding child is missing. The tree is constructed starting with the first tuple, which represents the root node. Your task is to build this binary tree and then compute the maximum sum of values along any path from the root to a leaf.

Formally, if (\mathcal{T}) is the given binary tree and each node (v) has a value (a_v), you need to compute:

[ \max_{\text{leaf } L} \sum_{v \in P(\text{root}, L)} a_v ]

where (P(\text{root}, L)) is the unique path from the root to the leaf node (L).

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains a single integer (n) ((1 \le n \le 10^5)), representing the number of nodes in the tree.

Each of the following (n) lines contains three space-separated tokens:

• The first token is an integer representing the node's value.
• The second token is either an integer (representing the value of the left child) or the string 'None' if the left child is missing.
• The third token is either an integer (representing the value of the right child) or the string 'None' if the right child is missing.

It is guaranteed that the first tuple corresponds to the root node.

outputFormat

Output to standard output (stdout) a single integer which is the maximum sum from the root to any leaf in the tree.## sample

5
1 2 3
2 4 5
3 None None
4 None None
5 None None

8