Grid Painting

题号：NC205330
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Recently, Little Gyro picked up several grids whose total number is n on the ground. As Little Gyro is bored, he decided to paint the grids with just two totally different colours, black and white. Here shows the picture of the grids after coloured:

Then, Little Gyro made another definition of the beauty value of those grids. At first, Little Gyro labelled these grids within the subscript from 1 to n, it means number i indicates the i-th grid. And he defined each grid contains two properties a and b, Property a indicates that if Little Gyro coloured the grid into black, it'll produce the beauty value of $a_i$ , and Property b indicates that if Little Gyro coloured the grid into white, it'll produce the beauty value of $b_i$ . After that, Little Gyro added up all the generated beauty value and obtained the total beauty value of all the grids.
What's more, Little Gyro also found that most of the grids had an additional property. The additional property of the i-th ( i ≥ 3 ) grid is described as a triple $(p_1,p_2,val)$ , indicating that if the i-th grid is currently coloured black, and at least one of the two subscripts $p_1$ , $p_2$ is coloured white, the summary of the beauty value will be reduced by val. And the two grids with the subscript 1 or 2 do not have this additional property.
Now given the total number of all the grids, Little Gyro wanted to colour all of them and tried to maximum the beauty value. Since there were too many situations to consider, Little Gyro couldn't solve the problem by himself. Please help him.

输入描述:

Each input file only contains one test case.
The first line contains an integer n (3 ≤ n ≤ 1000), indicating the total number of all the grids.
The second line contains n integers  (1 ≤  ≤ ), indicating the characteristic a of each grid.
The third line contains n integers  (1 ≤  ≤ ), indicating the characteristic b of each grid.
Then, the following n-2 lines, the (i+1)-th line contains three integers , ,  (1 ≤ ,  < i,  ≠ , 1 ≤  ≤ ), indicating the additional characteristic from the third grid to the n-th grid.

输出描述:

For each test case, output the maximum beauty value of all the given grids.

示例1

输入

复制

输出

复制