Cut the Tree

Given a graph with <b>N</b> vertices (labeled <b>1</b> to <b>N</b>). 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.</p>

<p>Follow the instruction below to "cut the tree" exactly <b>K</b> times:</p>

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

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

<p><b>Input</b></p>

<p>Mutiple test cases, process to the end of file.</p>

<p>Each test case consists of three parts.</p>

<p>First part, a single line with two integers <b>N</b> (1&lt;=N&lt;=1000) and <b>K</b> (0&lt;=K&lt;=20, K&lt;N).</p>

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

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

<p><b>Output</b></p>

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

<p><b>Sample Input</b></p>

<pre>
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
<!--
6 2
-3 1 -2 3 4 0
1 2
1 3
2 4
3 5
3 6
6 3
-3 1 -2 3 4 0
1 2
1 3
2 4
3 5
3 6
6 4
-3 1 -2 3 4 0
1 2
1 3
2 4
3 5
3 6
6 5
-3 1 -2 3 4 0
1 2
1 3
2 4
3 5
3 6
-->
</pre>

<p><b>Sample Output</b></p>

<pre>
-1 1
3 3
-1 4
<!--
-5 4
-5 4
-5 4
-3 4
-->
</pre>