Провинция Регион Соревнование Команда Игра
Как известно, соревнование ACM требует не только личных талантов, но и командной работы. Команда может быть успешной, если она объединяет оба этих аспекта.
В школе есть N кандидатов для участия в конкурсе ACM. Тренер хочет выбрать K кандидатов из N и отправить их на региональное соревнование в провинции Хунань. Предположим, что каждая команда состоит из 3 участников, и у каждого из них есть значение A, которое отражает его личные навыки. Каждая пара участников имеет значение W, которое показывает их навыки командной работы. Если в команде есть 3 участника 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), которые указывают количество команд и количество кандидатов. Вторая строка содержит N целых чисел A_1 ... A_n, (0 ≤ Ai ≤ 100000), представляющих личные навыки каждого кандидата. Следующие N строк содержат по N целых чисел, формирующих матрицу W_nn. W_ij описывает навыки командной работы между участниками i и j, 0 ≤ W_{ij }≤ 100000, и W_ij=W_ji.
Выходные данные
Для каждого случая выведите целое число, которое является максимальным счетом для K команд.