题目描述
图中共有N个点的完全图，每条边都有权值，每个点也有权值。要求选出M个点和M-1条边，构成一棵树，使得：
即所有边的权值比所有点的权值之和的比率最小。
给定N和M，以及N个点的权值，和所有的边权，要求M个点的最小比率生成树。输入
第一行包含两个整数N和M(2<=N<=15，2<=M<=N)，表示点数和生成树的点数。
接下来一行N个整数，表示N个点的边权。
最后N行，每行N列，表示完全图中的边权。所有点权和边权都在[1,100]之间。输出
输出最小比率生成树的M个点。当答案出现多种时，要求输出的第一个点的编号尽量小，第一个相同，则第二个点的编号尽量小，依次类推，中间用空格分开。编号从1开始。
样例输入 复制
3 2
30 20 10
0 6 2
6 0 3
2 3 0
样例输出 复制
1 3
提示
对于30%数据，N<=5。