As we know, ACM competition is not only based on personal talents, but also team works. A team can be outstanding once it combines these two factors.
A school has N ACM contest candidates. The coach wants to select K candidates from N candidates and sends them to Hunan Province Region Competition. We suppose every team has 3 members and every member has a value A that represents the personal skills. Every pair of members has a value W that shows the teamwork skills for that pair. There are 3 members a, b, c in a team then the integral skills of this team represents as following formula:
A[a]+A[b]+A[c]+W[a][b]+W[a][c]+W[b][c];
In the rules of Province Region Competition, team score is very important. A coach hope to set K teams up and the total team score is maximum.
Can you figure out what the maximum score of K teams if reasonably choosing team members from contest candidates?
The first line has a integer T (T ≤ 10) represents the number of cases. For each test cases, the first line has two numbers K, N (1 ≤ K ≤ 6, 3*K ≤ N ≤ 18) which show the number of teams and the number of candidates. The second line has N integers A_1 ... A_n, (0 ≤ Ai ≤ 100000) which represents the personal talent or personal skills for each candidates. The following N lines, every line has N integers which is a matrix W_nn. W_ij describe the teamwork skill between team member i and j, 0 ≤ W_{ij }≤ 100000,and W_ij=W_ji.
For every case, output a integer which is maximum score for K teams.