루미 알고리즘

#1470플래티넘Tree Advertisement

PO 2019 훈련 캠프코딩출제 Erik Amirell Eklöf영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
110N ≤ 15, B ≤ 500
210Each path has c_i = 1
310B ≤ 500, and each city has at most two adjacent roads.
415N ≤ 100, B ≤ 500, and each city has at most three adjacent roads, except city 1 which has at most two.
520N ≤ 100, B ≤ 500
635No 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

출처 표기

출처: Programmeringsolympiaden 2019년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.