나무 광고

아제르바이잔에는 $1$번부터 $N$번까지 번호가 붙은 $N$개의 도시가 있고, $N-1$개의 도로가 각 도시를 다른 모든 도시와 연결한다. 곧 수도 바쿠(1번 도시)에서 열리는 IOI를 보러 전국의 모든 사람이 자기 고향 도시에서 수도로 차를 타고 이동한다.

당신은 이 기회를 이용해 새로 만든 아주 똑똑한 프로그래밍 대회 채점기를 홍보하려고 여러 도로변의 나무에 광고판을 세우려 한다. 어떤 도로에 광고판을 세우면, 고향에서 수도로 가는 길에 그 도로를 지나는 모든 사람이 광고판을 보게 된다.

한 사람이 이동 중에 광고판을 두 번 이상 보아도 아무런 효과가 없다고 판단했다. 당신의 채점기는 한 번만 봐도 모두가 쓰고 싶어 할 만큼 인상적이다! 각 도로에 광고판을 세우는 데 드는 비용, 각 도시의 인구, 그리고 제한된 예산이 주어진다. 광고판을 최적으로 세울 때, 수도로 가는 길에 광고판을 하나 이상 보게 되는 사람 수의 최댓값은 얼마인가?

첫째 줄에 도시 수 $N$ ($1 \le N \le 2\,000$)과 크로나 단위의 예산 $B$ ($1 \le B \le 30\,000$)가 주어진다.

둘째 줄에 $N-1$개의 수 $p_2, p_3, \dots, p_N$ ($0 \le p_i \le 30\,000$)이 주어진다. $p_i$는 도시 $i$에 사는 사람 수이다.

다음 $N-1$개의 줄은 아제르바이잔의 모든 도로를 나타낸다. 이 중 $i$번째 줄에는 정수 $a_i, b_i$ ($1 \le a_i, b_i \le N$)와 $c_i$ ($1 \le c_i \le B+1$)가 주어지며, $i$번째 도로가 도시 $a_i$와 $b_i$를 잇고 그 도로에 광고판을 세우는 비용이 $c_i$ 크로나임을 뜻한다.

이 도로들을 이용해 모든 도시 사이를 이동할 수 있음이 보장된다.

광고판을 최적으로 세울 때, 광고판을 볼 수 있는 사람 수의 최댓값을 하나의 수로 출력한다.

첫 번째 예제에서는 1번 도시와 6번 도시 사이의 도로에 광고판 하나를, 2번 도시와 3번 도시 사이에 하나를 세우는 것이 최적이다. 비용은 $350 + 100$으로 예산 $500$ 안에 들어가고, 3, 4, 5, 6번 도시의 사람들이 광고를 보게 되어 모두 $1000 + 100 + 300 + 300 = 1700$명이 된다.