题目内容

多多村有 $N$ 个房子（编号 $1$~$N$），其中第 $i$ 个房子有权重 $W_i$。

同时，多多村恰好有 $N-1$ 条道路。每条道路连接相邻的两个房子，使得从一个房子到另外一个房子有且仅有唯一一条路径。

多多鸡打算重新规划多多村的道路建设，现在需要先拆除 $K$ 条道路。但由于拆除某条道路之后，当前原本相互联通的房子会分成 $2$ 个部分，并且它们之间不再相互通行。

而后续的拆除选择仅能从二者中选择其中一个部分继续进行（以此类推），因此需要谨慎选择拆除的顺序。

多多鸡想知道，在所有可能的拆除方案中，仍然相互联通的部分里的房子权重之和的最小值和最大值分别是多少。

输入描述

第一行，有 $2$ 个整数 $N$ 和 $K$，表示房子的数量和需要进行拆除的次数。（$1 \le N \le 1000, 0 \le K \le 50, K < N$） 第二行，有 $N$ 个整数 $W_i$，分别表示第 $i$ 个房子的权重。（$-1000 \le W_i \le 1000$） 接下来 $N-1$ 行，每行两个数字 $x$ 和 $y$，表示编号 $x$ 和编号 $y$ 的房子之间有一条道路。

输出描述

共 $1$ 行，有 $2$ 个整数，表示经过 $K$ 次拆除后，可能得到的最小值和最大值分别是多少。

样例1

输入

6 2
-3 1 -2 3 4 0
1 2
1 3
2 4
3 5
3 6

输出

-5 4

说明

可能的情况： 第一条选择拆除 $1-2$ 这条道路，分成了 $[2,4]$ 和 $[1,3,5,6]$ 两个部分

选择在$[1,3,5,6]$这个部分里继续进行

第二条选择拆除 $3-5$ 这条道路，分成了 $[5]$ 和 $[1,3,6]$ 这两个部分

在 $[1,3,6]$ 这个部分里，可以得到房子权重之和的最小值：$-3 + -2 + 0 = -5$

类似的，可以通过拆除$1$-$3$和$3$-$5$两条道路，得到 $[1,2,4]$,$[5]$ 和 $[3,6]$，其中 $[5]$

可以得到最大值: $4$