Poga The War Stopper

Poga is a war victim who lost everyone dear to her in war. Now, she leads a team of veterans who try to stop wars with minimum violence. But to do that, sometimes there is no option but to go a bit extreme.

Armed Combat Mercenaries (ACM) is a group of private soldiers who promote wars for their own profit. So, Poga and her group has set out to destroy their whole network to minimize their actions. ACM's network is in the same format as that of a tree. A tree is an acyclic undirected connected graph. For ease of work, Poga is planning strategies based on some calculation and processing of the tree.

Inside each vertex of the tree, there is a number and node 1 is the root of the tree. The cost of the whole tree can be defined as $AX^2 + B$ where $A$ and $B$ are two constants Poga knows from beforehand and $X$ is the sum of all the values of the vertices.

Now, if you cuts some edge of the tree, the tree will be split into 2 parts, each with its own cost. She is allowed to make as many cuts as she wishes. But all the cuts must be on same path from root in the original tree. That means, no two cut parts’ roots can have a lowest common ancestor that is not either of the two roots. Now, cutting this way, Poga can make many parts of the tree, find the cost of each part and sum them. What is the minimum sum can Poga make this way? Help her out find the answer, this will surely help in reducing wars!

Formally, given a rooted tree with weighted vertices, edges can be cut with the rule that all cuts must be on same path from root. Each cut splits the tree into 2 parts. There can be 0 or more cuts. Cost of each cut part is $AX^2 + B$ where $X$ is sum of all weights in the cut part and $A$, $B$ will be given as input. Your task is to minimize sum of costs of all cut parts.

Input

Input starts with an integer $T$ ($1 \le T \le 60$) denoting number of test cases.

Each case starts with 3 integers $N$, $A$, $B$. $N$ ($1 \le N \le 50000$) is the number of vertices and $A$ ($0 \le A \le 10000$), $B$ ($-10^6 \le B \le 10^6$) is defined in problem description. In next line, $N$ numbers will be given, $i$-th number ($0 \le \texttt{i-th number} ≤ 100$) represents the value of vertex $i$.

Then, in each of the next $N-1$ lines, 2 integers $U$ $V$ ($1 \le U, V \le N$, $U != V$) will be given denoting the 2 nodes connecting an edge of the tree. It is certain that the tree is a valid tree with all nodes connected and root is node 1.

Output

In a single line, print the minimum cost as asked in the problem statement.

Do this for each test case.

Sample

Input	Output
2 4 2 3 1 2 3 4 1 2 2 3 2 4 4 2 100 1 2 3 4 1 2 2 3 2 4	93 300

Dataset is huge. Use faster I/O.