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

В этой задаче на проверку необходимо сдать текстовый файл, соответствующий формату вывода. Входные данные расположены в файле "d2.txt" архива со входными данными. Скачать его можно, нажав на стрелку, расположенную в правом верхнем углу рядом с кнопкой «объявления жюри».

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

Формат ввода

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

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

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

Во второй строке задана перестановка из чисел от 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 дисков выведите время, необходимое для упорядочивания блоков данных.

Примечания

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

Во время тура проверяется, что файл содержит T T вещественных чисел.

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