Tree Subgraph Maximum Modulo Sum

Given a tree with \(n\) nodes, where node \(i\) has a weight \(a_i\), select a connected subgraph (i.e., a connected subset of nodes) such that the sum of the weights modulo \(M\) is maximized. In other words, if \(S\) is a connected subset of nodes, compute \(\left(\sum_{i \in S} a_i\right) \bmod M\) and find the maximum over all connected subsets.

Note: A connected subgraph is a subset of nodes such that for any two nodes in the subset, there exists a path between them using only the nodes from the subset.

inputFormat

The first line of input contains two integers \(n\) and \(M\), representing the number of nodes in the tree and the modulo value respectively. The second line contains \(n\) integers where the \(i\)-th integer is \(a_i\), the weight of node \(i\). Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) (1-indexed), representing an edge between node \(u\) and node \(v\>.

outputFormat

Output a single integer, the maximum possible value of \(\left(\sum_{i \in S} a_i\right) \bmod M\) taken over all connected subgraphs \(S\) of the tree.

sample

3 10
2 5 3
1 2
2 3

8