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 \textbf{N} ACM contest candidates. The coach wants to select \textbf{K} candidates from \textbf{N} candidates and sends them to Hunan Province Region Competition. We suppose every team has \textbf{3} members and every member has a value A that represents the personal skills. Every pair of members has a value \textbf{W} that shows the teamwork skills for that pair. There are \textbf{3} members \textbf{a}, \textbf{b}, \textbf{c} in a team then the integral skills of this team represents as following formula: \textbf{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 \textbf{K} teams up and the total team score is maximum. Can you figure out what the maximum score of \textbf{K} teams if reasonably choosing team members from contest candidates? \InputFile The first line has a integer \textbf{T} (\textbf{T} ≤ \textbf{10}) represents the number of cases. For each test cases, the first line has two numbers \textbf{K}, \textbf{N} (\textbf{1} ≤ \textbf{K} ≤ \textbf{6}, \textbf{3*K} ≤ \textbf{N} ≤ \textbf{18}) which show the number of teams and the number of candidates. The second line has \textbf{N} integers \textbf{A_1} ... \textbf{A_n}, (\textbf{0} ≤ \textbf{Ai} ≤ \textbf{100000}) which represents the personal talent or personal skills for each candidates. The following \textbf{N} lines, every line has \textbf{N} integers which is a matrix \textbf{W_nn}. \textbf{W_ij} describe the teamwork skill between team member \textbf{i} and \textbf{j}, \textbf{0} ≤ \textbf{W}_\{ij \}≤ \textbf{100000}，and \textbf{W_ij=W_ji}. \OutputFile For every case, output a integer which is maximum score for \textbf{K} teams.