Ariel is a travelling salesman in his own world. Ariel wants to buy some toys at city X and sells them at city Y (X can be equal to Y).

His own world forms a weighted tree.

The cost to travel from city X to city Y is the sum of weight of edge between city X and city Y.

You are given A[i], B[i].

A[i] denote the maximum number of toy that Ariel can buy at city i.

B[i] denote the price of buying / selling a toy in city i.

Ariel can choose two city. Let it be X and Y. such that he can buy some toy at city X, travel between X and Y, and sell some toy at city Y.

Ariel can only buy some toy at no more than one city, and can only sell some toy at no more than one city.

Help Ariel to maximize his profit.

Input

First line contains an integer N.

Second line contains N integer A[i].

Third line contains N integer B[i].

The next N-1 lines contains U V and W, there is an edge between U and V with weight W.

Output

One integer that denote maximum profit Ariel can get.

Constraint

2 <= N <= 1e5.

1 <= A[i], B[i], W<= 1e9.

1 <= U, V <= N

Example

Input:
4
10 10 10 10
5 5 5 5
1 2 1
2 3 1
3 4 1

Output:
0

Input:
5
1 9 4 16 5 
20 5 10 15 19 
2 1 6
2 3 6
2 4 7
3 5 4

Output:
129

Input:
10
9 7 5 19 7 2 10 7 2 4 
16 17 13 2 2 19 14 18 4 1
9 1 4
1 2 7
10 3 5
2 4 6
7 5 5
7 6 1
5 8 7
5 9 10
7 10 1

Output:
290