G. Optimal Deployment
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A software platform contains $$$N$$$ modules connected by $$$N-1$$$ bidirectional API links. The links form a connected graph with no cycles (a tree).

Choose any module as the root (the entry point). This determines a parent-child relationship for every link.

For a node $$$u$$$ in the rooted tree, let $$$subtreeSize(u)$$$ be the number of modules in the subtree rooted at $$$u$$$, including $$$u$$$ itself. Let $$$childCount(u)$$$ be the number of direct children of $$$u$$$.

There are $$$M$$$ types of deployment servers. Server type $$$i$$$ has capacity $$$C_i$$$ and costs $$$P_i$$$ per deployment operation. A server type can be reused any number of times, with its cost charged for each operation.

To deploy a module $$$u$$$, choose one of the following operations:

1. Deploy the entire subtree of $$$u$$$: One operation deploys $$$u$$$ and every descendant of $$$u$$$. The chosen server must have capacity $$$C_i \geq subtreeSize(u)$$$. No further operations are needed for any module in this subtree.

2. Deploy only $$$u$$$: One operation deploys $$$u$$$ and no other module. The chosen server must have capacity $$$C_i \geq childCount(u)$$$. Afterward, each direct child of $$$u$$$ must be deployed separately, using either operation.

Find the minimum total cost to deploy every module, choosing both the entry point and the server type for each operation optimally.

If deployment is impossible under every choice of entry point and available server types, output $$$-1$$$.

Input

The first line contains $$$T$$$ ($$$1 \leq T \leq 25$$$), the number of test cases.

For each test case:

The first line contains $$$M$$$ and $$$N$$$ ($$$1 \leq M,N \leq 10^5$$$), the number of server types and modules, respectively.

The second line contains the $$$M$$$ server capacities $$$C_1,C_2,\ldots,C_M$$$ ($$$1 \leq C_i \leq 10^9$$$).

The third line contains their corresponding costs $$$P_1,P_2,\ldots,P_M$$$ ($$$1 \leq P_i \leq 10^9$$$).

Each of the next $$$N-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq N$$$, $$$u \ne v$$$), describing a bidirectional API link between modules $$$u$$$ and $$$v$$$.

The sum of $$$M$$$ over all test cases does not exceed $$$5 \times 10^5$$$.

The sum of $$$N$$$ over all test cases does not exceed $$$5 \times 10^5$$$.

Output

For each test case, output one integer: the minimum total deployment cost, or $$$-1$$$ if deployment is impossible.

Example
Input
1
4 5
1 2 3 4
4 9 11 20
1 2
2 3
2 4
2 5
Output
24
Note

Choose module $$$1$$$ as the entry point.

Module $$$1$$$ has one direct child, so deploy only module $$$1$$$ using a server with capacity $$$1$$$ and cost $$$4$$$.

The subtree rooted at module $$$2$$$ contains modules $$$2,3,4,$$$ and $$$5$$$. Since $$$\text{subtreeSize}(2)=4$$$, deploy this entire subtree in one operation using a server with capacity $$$4$$$ and cost $$$20$$$.

The total cost is therefore $$$4+20=24$$$.