Description

A bandit syndicate holds great power in Green Shade Village. The whole Green Shade Village consists of $n$ connected hamlets, and it is guaranteed that for any two hamlets there is exactly one simple path between them. The hamlets are numbered from $1$ to $n$, and the syndicate’s headquarters is located in hamlet $1$.

Besides the boss stationed at the headquarters, the other $p$ departments want to establish branches elsewhere in the village (Luogu note: this actually also includes the headquarters). The $p$ branches can be built in the same hamlet or in different hamlets, and the cost of building different departments in different hamlets varies.

The path from each branch to the headquarters is defined as that department’s coverage. Therefore, the coverages of these $p$ branches may overlap or even be exactly the same. When multiple branches cover the same hamlet, conflicts may occur and cause some loss of profit, or cooperation may occur and generate some profit.

Please note that if the same set of branches simultaneously covers multiple hamlets, then the profit/loss for that set is counted once for each such hamlet.

Now you are to write a program to determine the locations of the $p$ branches so that the syndicate’s profit is maximized.

Input Format

• Line 1: Two integers $n$ and $p$, the number of hamlets and the number of departments.
• Lines $2$ to $n$: Each line contains two integers $x, y$, indicating a road between hamlet $x$ and hamlet $y$.
• Lines $(n + 1)$ to $2n$: Each line contains $p$ integers. On line $(i + n)$, the $j$-th integer is the cost $a_{i, j}$ of building department $j$ in hamlet $i$.
• Line $(2n + 1)$: An integer $t$, the number of inter-department influence items.
• Lines $(2n + 2)$ to $(2n + t + 1)$: Each line starts with an integer $v$; if $v$ is positive, extra profit is gained, and if $v$ is negative, a loss occurs. Then an integer $c$, the number of involved departments. Then $c$ integers, the involved departments $x_i$. The meaning is: if these $c$ departments simultaneously cover some hamlet (possibly along with other departments also covering that hamlet), then an extra profit or loss of $|v|$ is applied for each such hamlet.

Output Format

Output a single integer, the maximum achievable profit.

2 1
1 2
2 
1
1
3 1 1

5

Hint

Explanation for Sample 1:

If department $1$ is built at node $2$, the cost is $1$. Then the set of branches $\{1\}$ covers nodes $1$ and $2$. According to the first influence item, this set yields a profit of $3$ per covered node, so the total profit is $2 \times 3 = 6$. Subtracting the building cost, the maximum profit is $6 - 1 = 5$. It can be proven that no better plan exists.

Constraints:

• For $40\%$ of the testdata, $1 \leq p \leq 6$.
• For $100\%$ of the testdata, it is guaranteed that:
  • $1 \leq p \leq 12$, $1 \leq n \leq 100$.
  • $1 \leq a_{i, j} \leq 10^8$.
  • $1 \leq t \leq 2^p$, $1 \leq |v| \leq 10^8$, $1 \leq c \leq p$, $1 \leq x_i \leq p$, and the $x_i$ are pairwise distinct.
  • The absolute value of the answer does not exceed $10^8$.

Translated by ChatGPT 5