## YOSALES - Another Travelling Salesman Problem

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 4Output: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 1Output:290

Added by: | Ahmad Haulian Yoga Pratama |

Date: | 2018-04-21 |

Time limit: | 0.5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |

Resource: | ME |