在遥远的银河系中，有 $N$ 颗行星。第 $i$ 颗行星位于坐标 $(x_i, y_i, z_i)$。这些行星通过由 $N-1$ 条双向铁路组成的银河铁路系统相连，构成了一棵树。

作为银河探险局的代理人，你正在策划一场宣传活动。为了这次活动，你必须选择两颗行星进行重点宣传。游客可以通过以下两种不同的方式往返于这两颗行星之间：

• 银河列车：沿着铁路系统中连接这两颗行星的唯一简单路径行驶。每条铁路都有一个关联的满意度分数（可以是负数），总满意度为路径上所有分数之和。
• 私人火箭：沿着 $x, y, z$ 轴直接在两颗行星之间飞行。此选项的满意度分数等于两颗行星之间的曼哈顿距离，即 $|x_i - x_j| + |y_i - y_j| + |z_i - z_j|$。

为了满足两类游客，你需要选择一对行星 $(u, v)$，使得它们的组合满意度最大化。组合满意度定义为列车满意度与火箭满意度之和。

你的任务是求出这个最大组合满意度值。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 2 \cdot 10^5$)，表示行星的数量。

接下来的 $N-1$ 行，每行包含三个整数 $u, v$ 和 $w$，表示行星 $u$ 和行星 $v$ 之间有一条满意度分数为 $w$ 的铁路 ($1 \le u, v \le N, u \neq v, |w| \le 10^9$)。保证这些边构成一棵树。

接下来的 $N$ 行，每行包含三个整数 $x, y, z$，表示行星 $u$ 的坐标 ($1 \le x, y, z \le 10^{14}$)。

输出格式

输出一行一个整数，表示最大组合满意度值。

如果最大组合满意度小于零，则输出零。

样例

输入 1

5
1 2 -2
2 4 5
3 4 1
4 5 -5
8 3 2
7 6 1
8 6 2
3 6 3
1 1 1

输出 1

12

说明

对于样例，如果你选择行星 1 和行星 4，列车满意度等于 $-2 + 5 = 3$，火箭满意度等于 $|8 - 3| + |3 - 6| + |2 - 3| = 9$，组合满意度等于 $9 + 3 = 12$，可以证明这是最大值。