Input contains multiple test cases. The first line of each test case contains two integers n
<!-- MATH
$(2 \le n \le 15)$
-->
(2<=n<=15)

and m
<!-- MATH
$(2 \le m \le n)$
-->
(2<=m<=n)
, which stands for the number of nodes in the graph and the number of nodes in the minimal ratio tree. Two zeros end the input. The next line contains n
numbers which stand for the weight of each node. The following n

lines contain a diagonally symmetrical <!-- MATH
$n \times n$
-->
n×n
connectivity matrix with each element shows the weight of the edge connecting one node with another. Of course, the diagonal will be all 0, since there is no edge connecting a node with itself.

All the weights of both nodes and edges (except for the ones on the diagonal of the matrix) are integers and in the range of [1, 100].

The figure below illustrates the first test case in sample input. Node 1 and Node 3 form the minimal ratio tree.

<!-- MATH
$\epsfbox{p4326.eps}$
-->