Province Region Competition Team Play#3788
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 ACM contest candidates. The coach wants to select candidates from candidates and send them to Hunan Province Region Competition. We suppose every team has members and every member has a value that represents the personal skills. Every pair of members has a value that shows their teamwork skills. If there are members , , in a team, the integral skills of this team represents as following formula:
In the rules of Province Region Competition, team score is very important. The coach hopes to set up teams and the total team score is maximum.
Can you figure out what the maximum score of teams is if we reasonably choose team members from contest candidates?
The first line has a integer (T \leq 10) represents the number of cases. For each test cases, the first line has two numbers , (1 \leq K \leq 6, 3K \leq N \leq 18) which show the number of teams and the number of candidates. The second line has integers A_1 ... A_N, (0 \leq A_i \leq 100000) which represents the personal talent or personal skills for each candidates. The following lines, every line has integers which is a matrix W_{N \times N}. W_{ij} describe the teamwork skill between team member and , 0 \leq W_{ij} \leq 100000, and W_{ij}=W_{ji}.
For every case, output a integer which is maximum score for teams.
Example 1