Description

最近，网购在奇怪的大学里逐渐流行了起来. 为了解决同学们收快递不方便的难题，校方决定统一对校园的物流进行规划. 奇怪大学的校园里有N座宿舍，由N − 1条双向道路连接，每条双向道路的长度都为1，且每个宿舍都能走到其他任意宿舍. 现在学校准备在若干栋宿舍建立物流中心，建立每个物流中心的代价为K. 对于所有未设立物流中心的宿舍，就需要由邻近的物流中心进行配送，配送的代价与到物流中心的距离有关，若距离为i，则费用为Di. 现在我们需要确定一个最优的物流中心设置方案，使得设置物流中心和配送的总代价最小.

Input Format

第一行为两个整数N, K，分别表示宿舍的数目和建立物流中心的代价; 第二行有N − 1个整数D1, D2, ···, Dn−1，其中Di表示距离为i时的配送费用，且对于1 ≤ i < n − 1有Di ≤ Di+1; 接下来N − 1行，每个两个整数x, y，表示宿舍x和宿舍y之间有一条双向道路.

Output Format

输出一行，表示最小的总代价.

Sample

【样例输入】

8 10
2 5 9 11 15 19 20
1 4
1 3
1 7
4 6
2 8
2 3
3 5

【样例输出】

38

【样例解释】

我们可以选择在1和2号宿舍建立物流中心，此时3, 4, 7, 8号宿舍的配送距离为1，5, 6号宿舍的配送距离为2，
这样我们可以计算出总代价10 × 2 + 2 × 4 + 5 × 2 = 38，容易验证这是最小的.

Hint

对于30%的数据，有N ≤ 15; 对于另外20%的数据，每个宿舍至多与两个宿舍之间建立双向道路; 对于100%的数据，有1 ≤ N ≤ 200, 1 ≤ K ≤ 10^5, 1 ≤ Di ≤ 10^5.