에너지

악당 반 펠트는 게임기를 급히 충전해야 합니다. 이를 위해 에너지 공급원이 있는 지하 미로를 이용하려고 합니다.

미로에는 1번부터 $n$번까지 번호가 붙은 $n$개의 방이 있습니다. 일부 방 사이에는 복도가 있으며, 복도는 양방향으로 이동할 수 있습니다.

방 $a$와 방 $b$ 사이의 경로는 방들의 수열 $u_1, u_2, \dots, u_k$로서, $u_1 = a$, $u_k = b$이고, 모든 $1 \le i \le k - 1$에 대해 $u_i$와 $u_{i+1}$이 복도로 연결된 것을 말합니다. 임의의 두 방 사이에 경로가 정확히 하나 있으므로, 이 미로는 트리이며 복도는 정확히 $n-1$개입니다.

반 펠트는 어둡고 무서운 미로에 직접 들어가고 싶지 않습니다. 대신 $k$마리의 재규어를 보내 에너지를 가져오게 합니다. 재규어마다 반 펠트가 방 쌍(같은 방일 수도 있음)을 하나 고르면, 재규어는 그 두 방 사이 경로 위의 모든 방을 지납니다(고른 두 방 포함). 재규어는 매우 공격적이어서, 선택한 두 경로가 방을 하나라도 공유하면 재규어끼리 싸울 수 있습니다. 반 펠트는 재규어를 반드시 전부 보내야 합니다.

$i$번 방의 에너지 공급원에는 $a_i$만큼의 에너지가 들어 있습니다. 공급원의 에너지는 음수일 수도 있습니다. 각 재규어는 지나가는 모든 방의 공급원에서 에너지를 가져갑니다. 반 펠트가 받는 에너지는 재규어들이 가져간 에너지의 총합입니다.

반 펠트가 받을 수 있는 에너지의 최댓값을 구하세요.

첫째 줄에 방의 개수 $n$과 재규어의 수 $k$가 주어집니다 ($1 \le n \le 1000$, $1 \le k \le n$).

둘째 줄에는 각 방 공급원의 에너지 $a_i$가 공백으로 구분되어 $n$개 주어집니다 ($-10^9 \le a_i \le 10^9$).

이후 $n-1$개의 줄에는 복도로 연결된 두 방의 번호 $u_i$와 $v_i$가 주어집니다.

반 펠트가 받을 수 있는 에너지의 최댓값을 정수 하나로 출력하세요.

문제의 예시 상황에서 반 펠트는 한 재규어를 3번 방과 7번 방 사이 경로로, 다른 재규어를 5번 방과 6번 방 사이 경로로 보낼 수 있습니다. 그러면 재규어들은 3, 7, 5, 4, 6번 방을 지나며 에너지 14를 모읍니다.