你正在访问一个拥有 $N$ 座岛屿的公园。从每座岛屿 $i$ 出发，都恰好建造了一座桥梁，该桥梁的长度记为 $L_i$。公园内桥梁的总数为 $N$。虽然每座桥梁最初是从一座岛屿通往另一座岛屿建造的，但现在每座桥梁都可以双向通行。此外，对于每一对岛屿，都有唯一的轮渡往返于它们之间。

由于你更喜欢步行而不是乘坐轮渡，你希望在满足以下约束条件的前提下，最大化你所经过桥梁的长度之和。

• 你可以选择任意一座岛屿作为起点。
• 你不能访问任何岛屿超过一次。
• 在任何时候，你都可以从当前所在的岛屿 $S$ 移动到另一座你尚未访问过的岛屿 $D$。你可以通过以下两种方式之一从 $S$ 到达 $D$：
  • 步行：仅当两座岛屿之间有桥梁时才可行。选择此选项时，桥梁的长度会累加到你的总步行距离中。
  • 轮渡：仅当无法通过任何桥梁和/或之前使用过的轮渡组合从 $S$ 到达 $D$ 时，你才能选择此选项。（在检查是否可达时，你需要考虑所有路径，包括经过你已经访问过的岛屿的路径。）

注意，你不必访问所有的岛屿，而且可能无法走过所有的桥梁。

任务

编写一个程序，给定 $N$ 座桥梁及其长度，计算在遵守上述规则的情况下，你所能步行的最大距离。

数据范围

$2 \le N \le 1,000,000$：公园内岛屿的数量。 $1 \le L_i \le 100,000,000$：桥梁 $i$ 的长度。

输入格式

你的程序必须从标准输入读取以下数据：

• 第 1 行包含一个整数 $N$，表示公园内岛屿的数量。岛屿编号为 $1$ 到 $N$（包含 $1$ 和 $N$）。
• 接下来的 $N$ 行，每行描述一座桥梁。第 $i$ 行描述从岛屿 $i$ 出发建造的桥梁，包含两个由空格分隔的整数。第一个整数表示桥梁另一端的岛屿编号，第二个整数表示桥梁的长度 $L_i$。你可以假设对于每座桥梁，其两端始终是两座不同的岛屿。

输出格式

你的程序必须向标准输出写入一行，包含一个整数，即可能的最大步行距离。

说明

• 对于某些测试用例，答案可能无法用 32 位整数存储，你可能需要在 Pascal 中使用 int64 或在 C/C++ 中使用 long long 以获得满分。
• 在竞赛环境中运行 Pascal 程序时，从标准输入读取 64 位数据类型比读取 32 位数据类型要慢得多，即使读取的值在 32 位范围内也是如此。我们建议你将输入数据读取为 32 位数据类型。

子任务

对于某些总分 40 分的测试用例，$N$ 不超过 4,000。

样例

样例输入 1

7 
3 8 
7 2 
4 2 
1 4 
1 9 
3 4 
2 3

样例输出 1

24

说明

样例中 $N=7$ 座桥梁分别为 (1-3), (2-7), (3-4), (4-1), (5-1), (6-3) 和 (7-2)。注意，连接岛屿 2 和 7 的桥梁有两条。

实现最大步行距离的一种方式如下： 从岛屿 5 出发。 步行经过长度为 9 的桥到达岛屿 1。 步行经过长度为 8 的桥到达岛屿 3。 步行经过长度为 4 的桥到达岛屿 6。 乘坐轮渡从岛屿 6 到达岛屿 7。 步行经过长度为 3 的桥到达岛屿 2。

最终你停留在岛屿 2，总步行距离为 $9+8+4+3 = 24$。 唯一未被访问的岛屿是岛屿 4。注意，在上述行程结束时，你无法再访问该岛屿。更具体地说： 你无法通过步行访问它，因为当前所在的岛屿 2 与岛屿 4 之间没有桥梁。 你无法通过轮渡访问它，因为从你当前所在的岛屿 2 可以到达岛屿 4。一种到达方式是：使用桥梁 (2-7)，然后使用你之前从岛屿 7 到达岛屿 6 时使用过的轮渡，接着经过桥梁 (6-3)，最后经过桥梁 (3-4)。