Description

R and player B are playing a game. The game map consists of $N$ points and $N-1$ undirected edges, each connecting two points, and the map is connected. In other words, the map is a tree with $N$ nodes.

There is an item called a scout ward. When a player places a scout ward at a point, it can monitor that point and all points whose distance from it is within $D$. The distance between two points is defined as their distance on the tree, i.e., the number of edges on the unique simple path between them. Placing a scout ward at a point has a certain cost, and the cost may differ between points.

Now R knows all the positions where player B may appear. Please compute the minimum total cost to monitor all these positions.

Input Format

The first line contains two positive integers $N$ and $D$, denoting the number of points on the map and the vision range of a scout ward, respectively. Points are numbered from $1$ to $N$.

The second line contains $N$ positive integers. The $i$-th integer denotes the cost $W_i$ of placing a scout ward at point $i$. It is guaranteed that $W_i \le 1000$.

The third line contains a positive integer $M$, denoting the number of points where player B may appear. It is guaranteed that $M \le N$.

The fourth line contains $M$ positive integers, denoting the indices of the points where player B may appear, given in strictly increasing order without repetition.

The next $N-1$ lines each contain two positive integers $U, V$, indicating that there is an undirected edge between points $U$ and $V$.

Output Format

Output a single integer on one line, the minimum total cost required to monitor all points where player B may appear.

12 2
8 9 12 6 1 1 5 1 4 8 10 6
10
1 2 3 5 6 7 8 9 10 11
1 3
2 3
3 4
4 5
4 6
4 7
7 8
8 9
9 10
10 11
11 12

10

Hint

For all testdata, $N \le 5 \times 10^5$, $D \le 20$.

Translated by ChatGPT 5