Disjoint Chain and Interval

You are given a tree with n nodes and a sequence of length m. Each node i of the tree has a unique color \(c_i\) and a value \(a_i\). The tree is given with n-1 edges and it is guaranteed that the number of leaves does not exceed \(20\).

The sequence consists of m elements; the i-th element has a unique color \(d_i\) (unique within the sequence) and a value \(b_i\). Note that a color may appear both in the tree and in the sequence.

Your task is to select a simple path (chain) in the tree and a contiguous subarray (interval) in the sequence so that no color appears in both selections (i.e. the set of colors from the chosen tree nodes and the set of colors from the chosen sequence elements must be disjoint). The goal is to maximize the sum of the values from both selections.

Formal Description:

• The tree has n nodes. For each node \(i\), you are given its color \(c_i\) and value \(a_i\). All the \(c_i\) are distinct.
• The tree structure is provided by \(n-1\) edges.
• The sequence has m elements. For each element \(i\), you are given its color \(d_i\) and value \(b_i\). All the \(d_i\) are distinct.
• You need to choose a nonempty simple path in the tree and a nonempty contiguous subarray in the sequence such that if \(S\) is the set of colors on the tree path and \(T\) is the set of colors in the sequence interval, then \(S \cap T = \emptyset\).
• Let \(\sum_{i \in \text{chain}} a_i\) be the sum of values on the tree path, and \(\sum_{j \in \text{interval}} b_j\) be the sum of values in the subarray. You are to maximize \(\text{total} = \sum_{i \in \text{chain}} a_i + \sum_{j \in \text{interval}} b_j\).

Input Format: The input is given as follows:

• The first line contains two integers \(n\) and \(m\).
• The next \(n\) lines each contain two integers \(c_i\) and \(a_i\) for \(i = 1,2,\ldots,n\).
• The following \(n-1\) lines each contain two integers \(u\) and \(v\) representing an edge between nodes \(u\) and \(v\).
• The next \(m\) lines each contain two integers \(d_i\) and \(b_i\) for \(i = 1,2,\ldots,m\).

Output Format: Output a single integer representing the maximum possible sum of the values from a valid selection of a chain and an interval.

inputFormat

The first line contains two integers \(n\) and \(m\).

The next \(n\) lines each contain two integers \(c_i\) and \(a_i\), the color and value of the \(i\)-th node in the tree.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), representing an edge between nodes \(u\) and \(v\).

The following \(m\) lines each contain two integers \(d_i\) and \(b_i\), the color and value of the \(i\)-th element in the sequence.

outputFormat

Output a single integer: the maximum total value (sum of the chosen chain and the chosen interval) satisfying the disjoint color condition.

sample

3 3
1 1
2 2
3 3
1 2
2 3
4 10
2 -1
5 5

16