Energy

Villain Van Pelt needs to charge his game console urgently. For this, he uses an underground maze with energy sources.

The maze has $n$ rooms numbered from 1 to $n$. Some pairs of rooms are connected by corridors, which can be traveled in both directions.

A path between rooms $a$ and $b$ is a sequence of rooms $u_1, u_2, \dots, u_k$ where $u_1 = a$, $u_k = b$, and for every $1 \le i \le k - 1$, rooms $u_i$ and $u_{i+1}$ are connected by a corridor. Any two rooms have exactly one path between them, so the maze is a tree with exactly $n-1$ corridors.

Van Pelt does not want to enter the dark, frightening maze himself. Instead, he sends $k$ jaguars to fetch energy. For each jaguar, Van Pelt chooses a pair of rooms (possibly the same room), and the jaguar walks through every room on the path between them, including the chosen rooms. The jaguars are aggressive, so no two chosen paths may share a room, or the jaguars may fight. Van Pelt must send every jaguar.

Each room has an energy source holding $a_i$ units of energy in room $i$. A source may hold negative energy. Each jaguar takes the energy from every source on its path. The energy Van Pelt receives is the total energy taken by the jaguars.

Find the maximum amount of energy Van Pelt can receive.

The first line contains two integers $n$ and $k$ ($1 \le n \le 1000$, $1 \le k \le n$), the number of rooms and the number of jaguars.

The second line contains $n$ integers $a_i$ ($-10^9 \le a_i \le 10^9$), separated by spaces.

Each of the next $n-1$ lines contains two integers $u_i$ and $v_i$, the rooms connected by a corridor.

Print a single integer, the maximum amount of energy Van Pelt can receive.

In the sample from the statement, Van Pelt can send one jaguar on the path between rooms 3 and 7 and another on the path between rooms 5 and 6. The jaguars then cover rooms 3, 7, 5, 4, and 6, collecting 14 units of energy.