问题描述

给定一棵包含 $n$ 个结点的树，找出 $3$ 条边使得这三条边的端点仅经过这三条边即可互相到达且三条边的长度和尽可能大。

输入格式

输入第一行包含一个整数 $n$ 表示树的结点数。

接下来 $n−1$ 行，每行包含两个整数，用一个空格分隔。其中第 $i$ 行的两个数 $x_i,y_i$​，表示编号为 $i+1$ 和 $x_i$​ 的结点之间有一条长度为 $y_i$​ 的边。

输出格式

输出一行，包含一个整数表示满足要求的三条边的长度之和的最大值。

样例

5
1 1
2 1
3 7
1 10

12

样例说明

结点 $2$ 和结点 $1$ 的边长为 $1$，结点 $3$ 和结点 $2$ 的边长为 $1$，结点 $4$ 和结点 $3$ 的边长为 $7$，结点 $5$ 和结点 $1$ 的边长为 $10$。

评测用例规模与约定

对于 $20\%$ 的评测用例，$4≤n≤300$;

对于 $40\%$ 的评测用例，$4≤n≤5000$;

对于所有评测用例，$4≤n≤2×10^5$，$1≤x_i<i,1≤y_i≤10^9$。