Быстрый доступ - 1

Ограничение времени3 секунды
Ограничение памяти256 Мб
Вводстандартный ввод
Выводстандартный вывод

В этой задаче на проверку необходимо сдать программу, которая будет решать поставленную задачу.

Всем известно, что последовательный доступ к данным намного быстрее произвольного. Данные, хранящиеся на диске, разделены на N N блоков одинакового размера. Блоки данных занумерованы числами от 1 1 до N N и размещены на N N позициях на диске, которые также занумерованы числами от 1 1 до N N . Единственная разрешенная операция — обмен блоков данных на двух позициях. Для каждой пары позиций задано время, необходимое для обмена блоков данных, расположенных на этих позициях. Для оптимизации производительности чтения данных на каждом из T T дисков сервера необходимо переупорядочить блоки данных таким образом, чтобы их номера образовывали возрастающую последовательность.

Формат ввода

В первой строке вводится число T T ( 1 T 5 1 \le T \le 5 ) — количество дисков на сервере.

Далее следует T T описаний дисков.

В первой строке каждого описания содержится число N N ( 2 N 7 2 \le N \le 7 ) — количество позиций для хранения блоков данных на этом диске.

Во второй строке задана перестановка из чисел от 1 1 до N N  — номера блоков, в том порядке, в котором они размещены на позициях.

В следующих N N строках содержится матрица A A , описывающая время обмена блоков данных. Целое число A i , j A_{i, j} , где i i  — номер строки, а j j  — номер столбца при нумерации с единицы, задает время обмена блоков данных, расположенных на позициях i i и j j . При этом A i , j = A j , i A_{i, j} = A_{j, i} . Числа A i , j A_{i, j} не превосходят 1000.

Формат вывода

Для каждого из T T дисков выведите время, необходимое для упорядочивания блоков данных.

Пример

ВводВывод
3
2
2 1
0 1
1 0
3
1 2 3
0 9 4
9 0 6
4 6 0
3
2 3 1
0 1 10
1 0 6
10 6 0
1
0
7

Примечания

Оценка за эту задачу — 50 баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).

Каждое верно определенное время оценивается в 5 баллов.