Maximizing the Profits in a Village Network

In this problem, you are given an undirected tree with n nodes that represent connected villages. The villages are numbered from 1 to n and village 1 is the headquarters. Each village v has an associated value \(a_v\), which represents the profit (or loss) obtained from that village.

There are p departments (branches) that need to be established. Placing a department in village v incurs a cost \(c_{i,v}\) (this cost may vary for different departments and villages). The jurisdiction of a department placed at village \(v\) is defined as the unique simple path from village \(v\) to the headquarters (village 1). When a village is covered by one or more departments, its profit or loss is counted separately for each covering.

The contribution (profit) of a department i placed at village v is computed as:

[ \text{Profit}i = f(v) - c{i,v}, \quad \text{where} \quad f(v) = \sum_{u \in P(v)} a_u ]

Here, \(P(v)\) is the set of villages on the simple path from village \(v\) to the headquarters (including both endpoints). The total profit is the sum of the contributions of the p departments.

Your task is to choose a placement for each of the p departments (each can be placed in any village, and multiple departments can be placed in the same village) to maximize the total profit:

[ \text{Total Profit} = \sum_{i=1}^{p}\Big( f(v_i) - c_{i,v_i} \Big) ]

You are to output the maximum total profit.

inputFormat

The first line contains two integers n and p where n is the number of villages and p is the number of departments to be placed.

The next n−1 lines each contain two integers u and v, indicating an edge between village u and village v.

The following line contains n integers: a₁, a₂, ..., a_n, where a_v is the profit (or loss) of village v.

Then, there are p lines; each of these lines contains n integers. In the i-th line, the j-th integer represents the cost \(c_{i,j}\) to place department i in village j.

outputFormat

Output a single integer representing the maximum total profit achievable by optimally placing the p departments.

sample

5 2
1 2
1 3
2 4
2 5
3 -1 2 4 -2
5 2 3 10 1
4 3 2 8 0

5