You are given an unrooted tree with $n$ nodes. Each edge in the tree has a color. There are $m$ colors in total, numbered from $1$ to $m$. The weight of the $i$-th color is $c_i$. For any simple path in the tree, the edges on the path form a sequence of colors in order. This sequence can be partitioned into several contiguous segments of the same color. The weight of the path is defined as the sum of the weights of the colors of each monochromatic segment. Calculate the maximum path weight among all simple paths that have a number of edges between $l$ and $r$ (inclusive).

Input

The first line contains four integers $n, m, l, r$. The second line contains $n$ integers $c_1, c_2, \dots, c_m$, separated by spaces, representing the weight of each color. The next $n-1$ lines each contain three integers $u, v, c$, representing an edge between node $u$ and node $v$ with color $c$.

Output

Output a single integer representing the answer.

Examples

Input 1

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

Output 1

-2

Note 1

All color weights are negative; the optimal paths are $(1, 2)$ or $(1, 3)$.

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

Output 2

11

Note 2

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

Constraints

There are 10 test cases in total. The following table shows the constraints for each test case:

For 100% of the data, $1 \le n, m \le 2 \cdot 10^5$, $1 \le l \le r \le n$, $|c_i| \le 10^4$. It is guaranteed that there exists at least one path in the tree with a number of edges between $l$ and $r$.