Time Limit: 15000 mSec Memory Limit : 32768 KB

Given a Tree of N nodes.

Each node has exactly two labels.(0 and 1).

You must choose which label to assign to give the minimum cost.

The Cost is the sum of two parts:

1. For each node their is a cost assigned to the node for a given label.

2. For each pairs of Node connected their is a cost assigned to it according to it's labels.

In the first line, there are a number T(<=50) denotes the number of test cases.

In the second line, there are a number N(<=200000) denoting the number of Nodes.

In the third line, N numbers denoting the cost for each node assigned to label 0.

In the fourth line, N numbers denoting the cost for each node assigned to label 1.

In the next n-1 lines. each line containing six numbers P Q A B C D, P Q indicates there is a edge between P and Q , and A B C D are cost assigned to pairs of nodes which label is 00 01 10 11 accordingly.

The Tree root is always Node 1

Every cost is between 0 and 100

only 2 big cases

The Minimum cost of the given tree.(A Integer)

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

8