추격

고양이 톰이 또 생쥐 제리를 쫓고 있다. 제리는 톰이 따라오기 어렵도록 비둘기 떼 속으로 뛰어들려 한다. 마침 제리가 도착한 곳은 류블랴나의 중앙 공원이다. 공원에는 $1$번부터 $n$번까지 번호가 붙은 동상 $n$개가 있고, 서로 교차하지 않는 통로 $n-1$개가 동상을 이어 준다. 이 통로를 따라가면 어느 동상에서든 다른 모든 동상에 갈 수 있다. $i$번 동상 주위에는 비둘기가 $p_i$마리 몰려 있다.

제리의 주머니에는 빵부스러기가 $v$개 들어 있다. 제리가 지금 서 있는 동상 옆에 빵부스러기를 하나 떨어뜨리면, 통로로 곧바로 이어진 이웃 동상의 비둘기가 모두 즉시 이 동상으로 날아와 빵부스러기를 먹는다. 그래서 이 동상과 이웃 동상 주위의 비둘기 수 $p$가 바뀐다.

일은 다음 순서로 일어난다. 먼저 제리가 $i$번 동상에 도착해 그곳에 있는 비둘기 $p_i$마리를 만난다. 그다음 빵부스러기를 떨어뜨린다. 그리고 동상을 떠난다. 이웃 동상의 비둘기는 제리가 다음 동상에 도착하기 전에 $i$번 동상으로 옮겨 온다. 그래서 이 비둘기는 제리가 만난 비둘기 수에 들어가지 않는다.

제리는 아무 동상에서나 공원에 들어가 통로를 따라 달릴 수 있지만, 같은 통로를 두 번 지날 수는 없다. 그리고 원하는 곳 어디에서나 공원을 빠져나간다. 제리가 나간 뒤 톰이 들어와 똑같은 경로를 그대로 따라간다. 제리는 빵부스러기를 최대 $v$개 떨어뜨려서, 톰이 경로에서 만나는 비둘기 수와 자신이 만난 비둘기 수의 차이를 최대로 만들려고 한다. 제리가 만난 비둘기 수에는 그가 각 동상에 도착하기 바로 직전에 그 동상에 있던 비둘기만 센다.

첫째 줄에 동상의 수 $n$과 빵부스러기의 수 $v$가 주어진다. 둘째 줄에 정수 $n$개 $p_1$부터 $p_n$까지가 공백으로 구분되어 주어진다. 다음 $n-1$개 줄에는 각각 정수 $a_i$와 $b_i$가 주어지며, $a_i$번 동상과 $b_i$번 동상을 잇는 통로가 있다는 뜻이다.

톰이 만나는 비둘기 수와 제리가 만나는 비둘기 수의 차이의 최댓값을 정수 하나로 출력한다.

• $1 \le n \le 10^5$
• $0 \le v \le 100$
• $0 \le p_i \le 10^9$

첫 번째 예제에서 최적인 경로 하나는 다음과 같다. 제리는 6번 동상으로 공원에 들어가 그곳에서 비둘기 5마리를 만난다. 빵부스러기를 떨어뜨리면 $p_6$은 27이 되고 $p_5 = p_7 = p_8 = p_9 = 0$이 된다. 이어서 7번 동상으로 달려가 비둘기 0마리를 만난다. 두 번째 빵부스러기를 떨어뜨리면 $p_7$은 41이 되고 $p_2 = p_4 = p_6 = p_{10} = 0$이 된다. 그리고 공원을 빠져나간다. 제리가 만난 비둘기는 $5 + 0 = 5$마리다. 톰은 같은 경로를 따라가며 $p_6 + p_7 = 0 + 41 = 41$마리를 만난다. 차이는 $41 - 5 = 36$이다.