22794_挑选集训队

集训队有n名队员，教练将从中选择m名队员参加即将在五月份举行的广东省大学生程序设计竞赛。每支参赛队伍由3名队员组成。如何进行选拔呢？教练想出了一个办法：首先对每位有意向参赛的队员进行充分了解。通过多次选拔赛，根据队员的表现给每位队员一个技能值A，表示参赛队员的个人水平。另外程序设计竞赛又是一个团队赛，因此团队间的配合也是非常重要的。通过平时与队员的沟通交流，老师给任意两位队员设置配合度W。假设每支队伍的队员编号为a, b, c，那么衡量一支队伍的综合能力得分的公式为：

A[a]+A[b]+A[c]+W[a][b]+W[a][c]+W[b][c]

根据这个规则，陈老师希望从集训队中选择K支参赛队伍，使K支参赛队综合能力总得分最大。

输入包含多组测试数据。数据第一行为整数T ( T ≤ 10 )，表示测试数据组数。对于每组测试数据，第一行包含两个整数K，N ( 1 ≤ K ≤ 6,  3*K ≤ N ≤ 18 )。K表示参赛队伍数，N表示集训队中队员数。第二行包含N个整数：A₁, A₂, A₃, … A_n (0 ≤ A_i ≤ 100000 )。A_i 表示每位队员的技能值。接下来的N行为队员间的配合矩阵W_nn。W_ij 表示队员i和队员j间的配合度( 0 ≤ W_ij ≤ 100000，Wi_j = W_ji )。

对于每组测试数据，输出所选K支参赛队伍的的总得分最大值。

1
1 4
10 10 10 11
0 15 5 0
15 0 15 15
5 15 0 5
0 15 5 0

66