Провінція Регіон Змагання Команда Гра#3788

Провінція Регіон Змагання Команда Гра

2 секунди

64 мегабайти

Складна

Як відомо, змагання ACM ґрунтується не лише на індивідуальних здібностях, а й на командній роботі. Команда може досягти успіху, якщо поєднує ці два аспекти.

У школі є $N$ кандидатів на участь у конкурсі ACM. Тренер хоче обрати $K$ кандидатів з цих $N$ і відправити їх на регіональний конкурс у провінції Хунань. Припустимо, що кожна команда складається з $3$ учасників, і кожен учасник має значення $A$ , яке відображає його особисті навички. Кожна пара учасників має значення $W$ , яке показує їхні навички командної роботи. Якщо в команді є $3$ учасники $a$ , $b$ , $c$ , то загальні навички цієї команди визначаються за формулою:

A_{a} + A_{b} + A_{c} + W_{ab} + W_{a c} + W_{b c}

A_a+A_b+A_c+W_{ab}+W_{ac}+W_{bc}

Згідно з правилами регіонального конкурсу, командний бал має велике значення. Тренер прагне сформувати $K$ команд так, щоб загальний командний бал був максимальним.

Чи можете ви визначити, який максимальний бал можуть отримати $K$ команд, якщо раціонально обрати учасників з кандидатів?

Вхідні дані

Перша строка містить ціле число $T$ ( $T \leq 10$ T \leq 10), яке вказує на кількість тестових випадків. Для кожного тестового випадку перша строка містить два числа $K$ , $N$ ( $1 \leq K \leq 6$ 1 \leq K \leq 6, $3 K \leq N \leq 18$ 3K \leq N \leq 18), які вказують на кількість команд і кількість кандидатів. Друга строка містить $N$ цілих чисел $A_{1}$ A_1 ... $A_{n}$ A_n, ( $0 \leq A_{i} \leq 100000$ 0 \leq A_i \leq 100000), що представляють особисті навички кожного кандидата. Наступні $N$ рядків, кожен з яких містить $N$ цілих чисел, утворюють матрицю $W_{nn}$ W_{nn}. $W_{ij}$ W_{ij} описує навички командної роботи між учасниками $i$ та $j$ , $0 \leq W_{ij} \leq 100000$ 0 \leq W_{ij} \leq 100000, причому $W_{ij} = W_{j i}$ W_{ij}=W_{ji}.

Вихідні дані

Для кожного випадку виведіть ціле число, яке є максимальним балом для $K$ команд.

Приклади

Приклад 1