Məsələlər
Province Region Competition Team Play
Province Region Competition Team Play
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.
Giriş verilənləri #1
1 1 4 10 10 10 11 0 15 5 0 15 0 15 15 5 15 0 5 0 15 5 0
Çıxış verilənləri #1
66