Cut the Tree

Given a graph with N vertices (labeled 1 to N). The graph is connected, undirected and acyclic, and also known as an "unrooted tree". Each vertex has a weight, which is an integer. The total weight of a tree, is the summation of the weight of all its vertices.

Follow the instruction below to "cut the tree" exactly K times:

(1) Choose an edge of the tree, and remove it.
(2) Choose and discard one of the two divided parts of the graph we get.
(3) Get a new unrooted tree.

Now you are asked to calculate, after all those done, the minimal and maximal weight of the tree we finally get.

Input

Mutiple test cases, process to the end of file.

Each test case consists of three parts.

First part, a single line with two integers N (1<=N<=1000) and K (0<=K<=20, K<N).

Second part, a single line with N integers, the weight of vertices labeled 1 to N. The weight is in range [-1000,1000].

Third part, N-1 lines, each line with two integers X and Y represents an edge between vertex X and vertex Y.

Output

For each test case, output one line with two integers, the minimal and maximal weight of the tree we finally get.

Sample Input

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

Sample Output

-1 1
3 3
-1 4