Maximum Color Segment Sum on Tree Paths

You are given an unrooted tree with n vertices and n - 1 edges. Each edge in the tree is painted with one of m colors, numbered from 1 to m. The i-th color is associated with a weight \(c_i\).

For any simple path in the tree, consider the sequence of colors of the edges along the path. This color sequence can be partitioned into several contiguous segments where all edges in each segment have the same color. The weight of a path is defined as the sum of the weights corresponding to the color of each segment. In other words, if the sequence of colors along a path is \(a_1,a_2,\dots,a_k\), then its weight is computed as:

[ \text{weight} = c_{a_1} + \sum_{i=2}^{k} \begin{cases} c_{a_i}, & \text{if } a_i \neq a_{i-1} \ 0, & \text{if } a_i = a_{i-1} \end{cases} ]

You are also given two integers \(l\) and \(r\). Consider all simple paths in the tree that use at least \(l\) edges and at most \(r\) edges. Your task is to compute the maximum path weight among these paths.

Note: A simple path is a path that does not repeat vertices.

inputFormat

The first line contains four integers \(n\), \(m\), \(l\), \(r\) (\(1 \leq n \leq 200\) for this problem, and \(1 \leq m \leq 10^5\) with additional constraints ensuring that a brute-force solution is acceptable for the given test cases).

The second line contains \(m\) integers: \(c_1, c_2, \dots, c_m\), where \(c_i\) is the weight of color \(i\).

Each of the following \(n-1\) lines contains three integers \(u\), \(v\) and \(col\) (\(1 \leq u,v \leq n\) and \(1 \leq col \leq m\)), indicating that there is an edge between vertex \(u\) and vertex \(v\) with color \(col\).

outputFormat

Output a single integer, the maximum path weight among all simple paths in the tree that have a number of edges between \(l\) and \(r\) (inclusive). If no such path exists, you may output a value according to the problem constraints (for example, -1).

sample

3 2 1 2
5 10
1 2 1
2 3 2

15