Kōkopu (Trout 1.5)

The trout were not the only fish population impacted by the Newfound Zealous Irradiating Corporation (NZIC) dumping large amounts nuclear waste into the local river. A large group of banded kōkopu was also rather vexed by this action. Given that their home is now hopelessly radioactive, they have decided to move further down the river, where they have found a cozy network of shallow (and most importantly inert) pools connected by tranquil streams. Specifically, there are $N$ pools, numbered from $0$ to $N-1$ and connected by $N-1$ streams. These streams can be easily traversed in either direction by the kōkopu.

Now the kōkopu are discussing their sleeping arrangements. Each kōkopu will select one pool in which they will sleep every night and no two kōkopu can share the same pool. However, to protect themselves from prey (or evil irradiating corporations), they want to make sure they stick together as a single group. Specifically, when in their sleeping arrangement, any kōkopu should be able to reach the pool of any other kōkopu by going only through inhabited pools.

Additionally, not all pools are created equally, some pools have some overhanging banks, fallen logs or large boulders — all of which are great for hiding in. To quantify this, the kōkopu have assigned to each pool a safety score. The safety score of a sleeping arrangement is simply the sum of the safety scores of all inhabited pools. To ensure maximum safety, the kōkopu want to find a sleeping arrangement that satisfies all the previous constraints and has the maximum possible safety score.

However, this problem is harder than they expected, as there are $M$ kōkopu, and many possible arrangements to try out. Feeling bad, since you were in part responsible for the initial incident, you decide to write a computer program to help solve their problem!

Input

• The first line of input will contain two space-separated integers $N$ and $M$ — the number of pools and the number of kōkopu respectively.
• The next line will contain $N$ space-separated integers $s_0, s_1, s_2, \ldots, s_{N-1}$ where $s_i$ is the safety score of the $i^\text{th}$ pool.
• The next $N-1$ lines will each describe a stream between two pools. The $i^\text{th}$ of these lines will consist of two space-separated integers $a_i,b_i$ indicating that there is a stream between pool $a_i$ and pool $b_i$.

Output

Output a single integer — the maximum possible safety score of any valid sleeping arrangement.

Constraints

• $1 \le M \le N \le 2,000$
• $0 \le s_i \le 10^9$ for all $i$
• $0 \le a_i, b_i < N$ and $a_i \neq b_i$ for all $0 \le i < N-1$

It is guaranteed that every pool is reachable from any other pool using some series of streams.

Subtasks

• Subtask 1 (+7%): $s_i = 1$ for all $i$
• Subtask 2 (+9%): The streams form a line. Specifically, $a_i = i$ and $b_i = i+1$ for all $i$
• Subtask 3 (+14%): $N \le 15$
• Subtask 4 (+13%): All pools are directly connected to exactly 1 or 2 streams, except pool 0, which may be connected to any number of pools.
• Subtask 5 (+15%): All pools are directly connected to exactly 1 or 3 streams, except pool 0, which is directly connected to exactly 2 pools.
• Subtask 6 (+11%): All pools are directly connected to at most 3 streams and pool 0 is connected to exactly 2 pools.
• Subtask 7 (+10%): $N \le 100$
• Subtask 8 (+21%): No further constraints.

Notes

If you are using Python and your solution is exceeding the time limit, try selecting Python 3.11 (PyPy 7.3.19) when submitting as this will generally make your code run faster. Although beware that your code may run slower with PyPy if you are using recursion.

If you are using a type sensitive language like C++, Java, or C then make sure to use a 64 bit integer type to avoid integer overflow. 64-bit integer types include long long for C or C++, and long for C# or Java.

Sample Explanations

Sample One

The first sample looks like below. There are four pools and two kokopu looking for a place to sleep. In the diagram, the black lines represent streams between pools and the numbers next to a pool represent the number of that pool (note that the safety score is not shown on this diagram). It is optimal for the kokopu to sleep in pools 1 and 3. This gives them a total safety score of $2+4=6$

Sample Two

The second sample looks like below. There are ten pools and six kokopu looking for a place to sleep. The optimal arrangement is shown below. Note that any kokopu can reach any other kokopu by going only through pools occupied by other kokopu.