Провінція Регіон Змагання Команда Гра
Як відомо, змагання 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 команд.