G. Galactic Adventure Agency
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a galaxy far, far away, there are $$$N$$$ planets. The $$$i$$$-th planet is located at coordinates $$$(x_i,y_i,z_i)$$$. The planets are connected by a galactic railway system consisting of $$$N-1$$$ bi-directional railways, forming a tree structure.

As an agent of the Galactic Adventure Agency, you are planning a promotional campaign. For this campaign, you must choose two planets to highlight. Wanderers can journey between these two planets in two different ways:

  • By galactic train: Traveling along the unique simple path that connects the two planets in the railway system. Each railway has an associated satisfaction score (it can be negative), and the total satisfaction is the sum of the scores along the path.
  • By private rocket: Traveling directly between the two planets along the $$$x$$$, $$$y$$$, and $$$z$$$ axes. The satisfaction score for this option is equal to the Manhattan distance between the two planets, i.e. $$$|x_i - x_j| + |y_i - y_j| + |z_i - z_j|$$$.

To please both types of tourists, you want to select a pair of planets $$$(u, v)$$$ that maximizes the combined satisfaction value, defined as the sum of the train satisfaction and the rocket satisfaction between them.

Your task is to find this maximum combined satisfaction value.

Input

The first line of input contains one integer $$$N$$$ ($$$2 \le N \le 2 \cdot 10^5$$$) — the number of planets.

Each of the next $$$N-1$$$ lines contains three integers, $$$u$$$, $$$v$$$, and $$$w$$$, — a railway between planet $$$u$$$ and planet $$$v$$$ with a satisfaction score of $$$w$$$ ($$$1\le u,v\le N , u \neq v, |w| \le 10^9$$$). It is guaranteed that these edges form a tree.

Each of the next $$$N$$$ lines contains three integers, $$$x$$$, $$$y$$$, and $$$z$$$ — the coordinates of the planet $$$u$$$ ($$$1\le x,y,z\le 10^{14}$$$).

Output

A line contains one integer — the maximum combined satisfaction value.

If the maximum combined satisfaction value is less than zero, output zero.

Example
Input
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
Output
12
Note

For the example, if you choose planet $$$1$$$ and planet $$$4$$$, the train satisfaction is equal to $$$-2+5=3$$$ and the rocket satisfaction is $$$|8-3|+|3-6|+|2-3| = 9$$$, the combined satisfaction is equal to $$$9+3=12$$$, which can be shown to be the maximum.