g7-07660. 选课 未做

学校开设了 $n$ 门课程，编号 $1$ 到 $n$。课程之间存在先修关系：除了课程 $1$ 以外，每门课恰有一门先修课。
如果课程 $u$ 是课程 $v$ 的先修课，那么想选 $v$ 必须先选 $u$（先修关系保证不会形成环）。

每门课程 $i$ 有 $w_i$ 个学分。你最多可以选 $k$ 门课，但必须满足先修关系。
请你求出最多能得到多少学分。

第一行两个正整数 $n,k$（$1\le k\le n\le 2000$）。

第二行 $n$ 个整数 $w_1,w_2,\dots ,w_n$（$0\le w_i\le 10^9$）。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示课程 $u$ 是课程 $v$ 的先修课。

一行一个整数，表示最多能获得的学分。

输入：

5 3
1 2 3 4 5
1 2
1 3
3 4
3 5

输出：

9

说明：先修树中 $1$ 是根，$3$ 的子节点是 $4,5$。选 $\{1,3,5\}$ 得 $1+3+5=9$，这是满足先修关系的最大方案。

子任务	数据点占比	$n$
1	20%	$\le 10$
2	20%	$\le 100$
3	60%	$\le 2000$