The traffic in country W is shaped like a tree. Country W has a total of $n-1$ cities and $n$ villages, where cities are numbered from $1$ to $n-1$ and villages are numbered from $1$ to $n$, with city $1$ being the capital. All roads are one-way; in this problem, we only consider the road network leading from villages to the capital. For every city, there is exactly one highway and one railway leading to it. For city $i$, the starting point of the road (highway or railway) leading to this city is either a village or a city with a number greater than $i$. No roads lead to any village. Except for the capital, every city or village has exactly one outgoing road; the capital has no outgoing roads. Starting from any village and following the unique outgoing road, one can always reach the capital.

King W of country W has received funding and decided to use it to improve traffic. Due to limited funds, King W can only renovate $n-1$ roads. King W decides to renovate exactly one road leading to each city, choosing either the highway or the railway. King W wants to make the journey from villages to the capital as convenient as possible. Based on population survey data, King W has set three parameters for each village; for the village numbered $i$, the three parameters are $a_i$, $b_i$, and $c_i$. Suppose that traveling from the village numbered $i$ to the capital requires passing through $x$ unrenovated highways and $y$ unrenovated railways, then the inconvenience value of that village is:

$$c_i \cdot (a_i + x) \cdot (b_i + y)$$

Under a given renovation plan, the sum of the inconvenience values of all villages is the inconvenience value of that renovation plan.

There are many ways to renovate $n-1$ roads, and the plan with the minimum inconvenience value is called the optimal renovation plan. King W naturally hopes to find the optimal renovation plan. Please help him calculate the inconvenience value of this optimal renovation plan.

Input

The input file is named road.in. The first line contains a positive integer $n$. The next $n-1$ lines each describe a city. The $i$-th line contains two numbers $s_i, t_i$. $s_i$ represents the starting point of the highway leading to city $i$, and $t_i$ represents the starting point of the railway leading to city $i$. If $s_i > 0$, there exists a highway from city $s_i$ to city $i$; otherwise, there exists a highway from village $-s_i$ to city $i$. Similarly, if $t_i > 0$, there exists a railway from city $t_i$ to city $i$; otherwise, there exists a railway from village $-t_i$ to city $i$. The next $n$ lines each describe a village. The $i$-th line contains three numbers $a_i, b_i, c_i$, with meanings as described in the problem.

Output

The output file is named road.out. Output a single integer representing the inconvenience value of the optimal renovation plan.

Examples

Input 1

6
2 3
4 5
-1 -2
-3 -4
-5 -6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Output 1

54

Note 1

As shown in the figure, we use blue and yellow nodes to represent cities and villages respectively; green and red arrows represent highways and railways respectively; bold arrows represent renovated roads.

One method with an inconvenience value of 54 is: renovate the railways leading to city 2 and city 5, and the highways leading to other cities. Using $\to$ and $\Rightarrow$ to represent highways and railways, and $*\to$ and $*\Rightarrow$ to represent renovated highways and railways, then:

• The route for village 1 to the capital is: $-1 *\to 3 \Rightarrow 1$, passing through 0 unrenovated highways and 1 unrenovated railway, cost $3 \times (1 + 0) \times (2 + 1) = 9$;
• The route for village 2 to the capital is: $-2 \Rightarrow 3 \Rightarrow 1$, passing through 0 unrenovated highways and 2 unrenovated railways, cost $2 \times (1 + 0) \times (3 + 2) = 10$;
• The route for village 3 to the capital is: $-3 *\to 4 \to 2 *\to 1$, passing through 1 unrenovated highway and 0 unrenovated railways, cost $3 \times (2 + 1) \times (1 + 0) = 9$;
• The route for village 4 to the capital is: $-4 \Rightarrow 4 \to 2 *\to 1$, passing through 1 unrenovated highway and 1 unrenovated railway, cost $1 \times (2 + 1) \times (3 + 1) = 12$;
• The route for village 5 to the capital is: $-5 \to 5 *\Rightarrow 2 *\to 1$, passing through 1 unrenovated highway and 0 unrenovated railways, cost $2 \times (3 + 1) \times (1 + 0) = 8$;
• The route for village 6 to the capital is: $-6 *\Rightarrow 5 *\Rightarrow 2 *\to 1$, passing through 0 unrenovated highways and 0 unrenovated railways, cost $1 \times (3 + 0) \times (2 + 0) = 6$;

The total inconvenience value is $9 + 10 + 9 + 12 + 8 + 6 = 54$. It can be proven that this is the optimal solution for this data.

Input 2

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

Output 2

548

Note 2

In this example, it is clearly optimal to renovate all highways.

Input 3

12
2 4
5 3
-7 10
11 9
-1 6
8 7
-6 -10
-9 -4
-12 -5
-2 -3
-8 -11
53 26 491
24 58 190
17 37 356
15 51 997
30 19 398
3 45 27
52 55 838
16 18 931
58 24 212
43 25 198
54 15 172
34 5 524

Output 3

5744902

Constraints

There are 20 test cases in total, numbered 1 to 20. For cases $\le 4$, $n \le 20$; For cases 5 to 8, $a_i, b_i, c_i \le 5$, $n \le 50$; For cases 9 to 12, $n \le 2000$; For all data, $n \le 20000$, $1 \le a_i, b_i \le 60$, $1 \le c_i \le 10^9$, $s_i, t_i$ are integers in $[-n, -1] \cup (i, n-1]$, and any village can reach the capital through no more than 40 roads.