题目描述

对于一个节点和边都带权的树，其比率（Ratio）按以下公式计算：

给定一个包含$n$个节点的完全图（所有节点和边都带权），你的任务是找到一个由$m$个节点构成的树（原图的子图），使得该树的比率是所有可能的$m$节点树中最小的。

输入：

输入包含多个测试用例。每个测试用例的第一行包含两个整数$n$（$2 \leq n \leq 15$）和$m$（$2 \leq m \leq n$），分别表示图中的节点数和最小比率树的节点数。两个$0$表示输入结束。接下来的一行包含$n$个整数，表示每个节点的权重。随后的$n$行是一个对角线对称的$n \times n$连通矩阵，每个元素表示连接两个节点的边的权重。矩阵的对角线元素均为$0$，因为节点不会与自己相连。

所有节点和边的权重（矩阵对角线元素除外）都是$[1, 100]$范围内的整数。

下图展示了样例输入中的第一个测试用例。节点$1$和节点$3$构成了最小比率树。

输出：

对于每个测试用例，输出一行，包含构成最小比率树的$m$个节点的编号。节点应按升序排列。如果有多个满足条件的序列，选择节点编号字典序最小的序列（即首先比较最小的节点编号，若相同则比较第二小的节点编号，以此类推）。注意节点编号从$1$开始。

输入样例 1：

3 2 
30 20 10 
0 6 2 
6 0 3 
2 3 0 
2 2 
1 1 
0 2 
2 0 
0 0

输出样例 1：

1 3 
1 2