时间限制:1000ms  空间限制:256MB

题目描述

图中共有 $N$ 个点的完全图，每条边都有权值，每个点也有权值。要求选出 $M$ 个点和 $M-1$ 条边，构成一棵树，使得下式最小：

$$Ratio = \frac{\sum{edge\_weight}}{\sum{node\_weight}} $$

  即所有边的权值比所有点的权值之和的比率最小。

输入格式

第一行包含两个整数 $N$ 和 $M(2<=N<=15，2<=M<=N)$，表示点数和生成树的点数。   接下来一行 $N$ 个整数，表示 $N$ 个点的边权。   最后 $N$ 行，每行 $N$ 列，表示完全图中的边权。所有点权和边权都在 $[1,100]$ 之间。

输出格式

输出最小比率生成树的 $M$ 个点。当答案出现多种时，要求输出的第一个点的编号尽量小，第一个相同，则第二个点的编号尽量小，依次类推，中间用空格分开。编号从 1 开始。

样例

输入#1

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

输出#1

1 3

数据范围/约定

对于30%数据，$N<=5$。 对于 100% 的测试数据满足：$2<=N<=15，2<=M<=N$。