Description

YSGH has a tree of size $n$ and a sequence of length $m$.

Each node $i$ in the tree has a color $c_i$ and a value $a_i$. All colors are pairwise distinct. It is guaranteed that the number of leaves does not exceed $\boldsymbol{20}$.

Each position $i$ in the sequence also has a color $d_i$ and a value $b_i$. All colors are also pairwise distinct (but colors in the tree and the sequence may be the same).

YSGH wants to choose a path (a chain) in the tree and a subarray (an interval) of the sequence such that each color appears at most once in total. He wants to know the maximum possible sum of values he can obtain.

Input Format

The first line contains two positive integers $n, m$, representing the size of the tree and the length of the sequence.

The next $n - 1$ lines each contain two positive integers $x, y$, representing an edge in the tree.

The next line contains $n$ positive integers; the $i$-th integer is $c_i$.

The next line contains $n$ positive integers; the $i$-th integer is $a_i$.

The next line contains $m$ positive integers; the $i$-th integer is $d_i$.

The next line contains $m$ positive integers; the $i$-th integer is $b_i$.

Output Format

Only one line containing one integer, representing the answer.

4 4
1 2
2 3
3 4
1 2 3 4
10 2 3 7
2 5 6 1
5 1 7 2

30

Hint

[Sample Explanation]

The optimal solution is to choose nodes $1, 2, 3, 4$ in the tree and positions $2, 3$ in the sequence.

The sum of values is $10 + 2 + 3 + 7 + 1 + 7 = 30$.

[Constraints]

This problem uses bundled testdata.

For $100 \%$ of the testdata, $1 \le n \le 5 \times {10}^4$, $1 \le m \le 5 \times {10}^5$, $1 \le c_i, d_i \le n + m$, $1 \le a_i, b_i \le {10}^9$, and it is guaranteed that the number of leaves in the tree does not exceed $20$.

• Subtask 1 (10 points): $n, m \le 500$.
• Subtask 2 (10 points): $n, m \le 1000$.
• Subtask 3 (10 points): $n, m \le 5000$.
• Subtask 4 (20 points): The $i$-th edge of the tree connects $i$ and $i + 1$.
• Subtask 5 (15 points): $m \le {10}^5$.
• Subtask 6 (35 points): No additional constraints.

Translated by ChatGPT 5