영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
In Azerbaijan there are N cities, numbered between 1 and N, connected by N - 1 roads in such a way that each pair of cities are connected by some sequence of roads. It's soon time for this year's International Olympiad in Informatics in the capital, Baku (city 1), and everyone in the whole country will then drive from their hometown to the capital to watch the contest.
You want to use this opportunity to advertise your new, really clever online programming judge by putting up advertisement posters on a lot of trees along different roads. If you put up posters along a road, everyone who travels along that road during the trip from their hometown to the capital will see the poster.
You have determined that it doesn't help if someone sees your posters more than once during their travels – your judge is so impressive that everyone wants to use it after seeing the poster just once! Each road has a certain cost for putting up a poster on all the trees along the road, each city has a given population, and you have a limited budget. If you put up the posters optimally, what's the greatest number of people who will see at least one poster on their way to the capital?
Input
The first line contains two integers N and B (1 ≤ N ≤ 2000, 1 ≤ B ≤ 30000), the number of cities and your budget in Swedish crowns.
The second line contains N-1 integers p_2, p_3, …, p_N (0 ≤ p_i ≤ 30000), where p_i is the population of the i'th city.
The following N-1 lines describe all the road in Azerbaijan. The i'th of these contains the integers a_i, b_i (1 ≤ a_i, b_i ≤ N) and c_i (1 ≤ c_i ≤ B+1), which means that the i'th road connects the cities a_i and b_i has a cost of c_i crowns to put up posters along.
It's guaranteed that a sequence of roads exist between any pair of paths.
Output
Output a single integer – the greatest number of people who can see your posters, if you put them up optimally.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
| Group | Points | Constraints |
| 1 | 10 | N ≤ 15, B ≤ 500 |
| 2 | 10 | Each path has c_i = 1 |
| 3 | 10 | B ≤ 500, and each city has at most two adjacent roads. |
| 4 | 15 | N ≤ 100, B ≤ 500, and each city has at most three adjacent roads, except city 1 which has at most two. |
| 5 | 20 | N ≤ 100, B ≤ 500 |
| 6 | 35 | No additional constraints. |
Explanation of sample
In the first sample case it's optimal to put up posters on the roads between city 1 and 6, and between city 2 and 3. This costs 350 + 100 (less than the budget of 500), and will result in everyone in cities 3, 4, 5 and 6 seeing the posters, a total of 1000 + 100 + 300 + 300 = 1700 people.
예제
예제 1
6 500 500 1000 100 300 300 1 2 200 3 2 100 1 6 350 5 6 501 6 4 250
1700
예제 2
6 4 10 20 30 40 50 1 2 1 1 3 1 1 4 1 2 5 1 3 6 1
150