For a rootless tree with vertices and edges, each edge has edge weights. In the beginning, each vertex has a color (black or white), you can choose to reverse the color of some vertex, but this will pay the .

For a tree, we define its as , where is the set of white vertices and is the set of black vertices.

Where is the maximum edge weight in the shortest path from to .

You need to reverse some vertices (or not) so that the is maximum? You need to calculate the answer.

输入描述:

The first line contains a positive integer , representing the number of vertices in the tree.

The second line contains a row of  integers , representing the initial color of the -th vertex ( for white,  for black).

The third line contains a row of  integers , representing the cost of changing the -th vertex.

The next  line, each line contains three positive integers  represents an undirected edge and edge weight. It is guaranteed that the input is a tree.

输出描述:

A line of output with an integer represents the maximum .

3
0 0 0
1 2 3
1 2 1
2 3 2

2

change the color of the first vertex

8
1 0 0 0 0 1 0 0
3 9 8 9 5 9 9 4
1 2 2
1 3 8
1 4 5
1 5 5
5 6 7
2 7 3
3 8 3

100