给你一棵 n 个点的无根树。

树上的每条边具有颜色。一共有 m 种颜色，编号为 1 到 m。第 i 种颜色的权值为 ci。

对于一条树上的简单路径，路径上经过的所有边按顺序组成一个颜色序列，序列可以划

分成若干个相同颜色段。定义路径权值为颜色序列上每个同颜色段的颜色权值之和。

请你计算，经过边数在 l 到 r 之间的所有简单路径中，路径权值的最大值。

第一行，四个整数 n, m, l, r。

第二行，m个整数 c1, c2, ……, cm，由空格隔开。依次表示每个颜色的权值。

接下来 n-1 行，每行三个整数

输出一行，一个整数，表示答案。

对于 100%的数据，1 ≤ n, m ≤ 2*10^5, 1 ≤ l ≤ r ≤ n, |ci| ≤ 10^4。保证 树上至少存在一条经过边数在 l 到 r 之间的路径。  

受NKOJ局限，强烈建议手工扩栈！