Problem Description

You are given an undirected tree with $n$ vertices.

Each edge in the tree has a color. There are $m$ different colors, numbered from $1$ to $m$, and the weight of the $i$-th color is $c_i$.

For a simple path in the tree, the edges on the path form a sequence of colors. This sequence can be divided into segments of the same color. The weight of the path is defined as the sum of the weights of the colors in each color segment.

Your task is to calculate the maximum path weight among all simple paths with edge counts between $l$ and $r$.

Input Format

The first line contains four integers $n$, $m$, $l$, and $r$.

The second line contains $m$ integers $c_1, c_2, \ldots, c_m$, separated by spaces, representing the weights of each color.

The following $n-1$ lines each contain three integers $u$, $v$, and $c$, indicating that there is an edge with color $c$ between vertex $u$ and vertex $v$.

Output Format

Output a single integer, which is the answer to the problem.

Sample Input and Output

Sample Input #1

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

Sample Output #1

-1

Sample Input #2

8 4 3 4
-7 9 6 1
1 2 1
1 3 2
1 4 1
2 5 1
5 6 2
3 7 1
3 8 3

Sample Output #2

11

Notes

Sample Explanation 1

All color weights are negative, and the optimal path is either $(1, 2)$ or $(1, 3)$.

Sample Explanation 2

The optimal path is $(3, 1, 2, 5, 6)$, with the color sequence $(2, 1, 1, 2)$.

Data Range

For $100\%$ of the data, $1 \leq n, m \leq 2 \times 10^5$, $1 \leq l \leq r \leq n$, $\mid c_i \mid \leq 10^4$. It is guaranteed that there is at least one path with edge count between $l$ and $r$.

见题面 Input 部分

见题面 Output 部分