배달원

크레쇼가 고추를 재배하기 시작한 뒤로, 크로아티아 전역의 식당 N곳이 요리에 진짜 매운맛을 내려고 크레쇼의 고추를 찾기 시작했다. 주문이 밀려들자 크레쇼는 고추 배달을 직접 하기로 했다.

식당에는 1번부터 N번까지 번호가 붙어 있고, 도로 $N - 1$개가 식당을 이어 어느 두 식당 사이든 오갈 수 있다. 크레쇼는 1번 식당에서 출발한다. 시간 1을 써서 크레쇼는 인접한 식당으로 이동하거나, 지금 있는 식당에 고추를 배달한다. 식당 i가 필요로 하는 고추의 양은 $A_i$이다. 한 식당에는 배달을 한 번만 하고, 그 한 번으로 그 식당이 필요로 하는 $A_i$를 모두 넘긴다.

배달은 고된 일이라 크레쇼는 이동과 배달에 시간을 모두 합쳐 M만큼만 쓰고 쉬기로 했다. 주어진 시간 안에 크레쇼가 배달할 수 있는 고추의 최대 양을 구하라. 크레쇼가 지고 다니는 고추는 무한하다고 가정한다.

첫째 줄에 식당의 수 N과 크레쇼가 배달에 쓰기로 한 시간 M이 주어진다. ($1 \le N, M \le 500$)

둘째 줄에 정수 $A_i$가 N개 주어진다. $A_i$는 i번 식당이 필요로 하는 고추의 양이다. ($1 \le A_i \le 10^6$, $1 \le i \le N$)

다음 $N - 1$개 줄에는 각각 정수 U와 V가 주어진다. U번 식당과 V번 식당을 잇는 도로가 있다는 뜻이다. ($1 \le U, V \le N$, $U \ne V$)

크레쇼가 주어진 시간 안에 배달할 수 있는 고추의 최대 양을 한 줄에 출력한다.

첫 번째 예제를 보자. 크레쇼는 1번 식당에 고추를 배달하고(시간 1), 3번 식당으로 이동한 다음(시간 1), 3번 식당에 고추를 배달한다(시간 1). 남은 시간은 2이고, 이 시간으로 2번 식당까지 갈 수는 있지만 거기에 배달할 시간 1이 모자란다.