나무 광고

아제르바이잔에는 $1$부터 $N$까지 번호가 매겨진 $N$개의 도시가 있으며, $N - 1$개의 도로가 모든 도시 쌍이 어떤 도로들의 연속으로 연결되도록 도시들을 잇고 있다. 곧 수도 Baku(도시 $1$)에서 올해의 정보학 International Olympiad가 열리며, 전국의 모든 사람이 대회를 관람하기 위해 고향에서 수도까지 차를 타고 이동할 것이다.

당신은 이 기회를 이용해 여러 도로를 따라 있는 많은 나무에 광고 포스터를 붙여 새롭고 매우 영리한 온라인 프로그래밍 채점 시스템을 홍보하려 한다. 어떤 도로를 따라 포스터를 붙이면, 고향에서 수도로 이동하는 동안 그 도로를 지나는 모든 사람이 포스터를 보게 된다.

당신은 누군가가 이동 중에 포스터를 두 번 이상 보더라도 도움이 되지 않는다는 사실을 알아냈다 -- 당신의 채점 시스템은 매우 인상적이어서 누구나 포스터를 단 한 번만 보고도 사용하고 싶어 하기 때문이다! 각 도로에는 그 도로를 따라 있는 모든 나무에 포스터를 붙이는 데 드는 비용이 정해져 있고, 각 도시에는 주어진 인구가 있으며, 당신에게는 한정된 예산이 있다. 포스터를 최적으로 붙인다면 수도로 가는 길에 적어도 하나의 포스터를 보게 되는 사람 수의 최댓값은 얼마인가?

채점

당신의 풀이는 각각 일정한 점수가 배정된 여러 테스트 그룹으로 평가된다. 한 테스트 그룹의 점수를 받으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다. 최종 점수는 단일 제출에서 받은 점수 중 최댓값이다.

그룹 | 점수 | 제한

$1$ |$10$| $N \le 15$, $B \le 500$

$2$ |$10$| 각 경로에는 $c_i = 1$

$3$ |$10$| $B \le 500$, 그리고 각 도시에는 인접한 도로가 최대 두 개 있다.

$4$ |$15$| $N \le 100$, $B \le 500$, 그리고 도시 $1$에는 인접한 도로가 최대 두 개 있고, 그 외의 각 도시에는 최대 세 개 있다.

$5$ |$20$| $N \le 100$, $B \le 500$

$6$ |$35$| 추가 제한 없음.

첫 번째 줄에는 도시의 수와 스웨덴 크로나 단위의 예산을 나타내는 두 정수 $N$와 $B$가 주어진다($1 \le N \le 2\,000$, $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$명이 된다.