РобоФест
Вы участвуете в соревновании по робототехнике "РобоФест". Ваш робот должен обойти все промежуточные пункты и вернуться в начало. У вас имеется карта местности и вы хотите найти наиболее оптимальный маршрут для вашего робота. Карта имеет вид прямоугольника N×M клеток, в каждой клетке записано положительное число - время, которое будет затрачено на прохождение этой клетки роботом. Также у вас есть список координат промежуточных пунктов и точки начала.
Входные данные
В первой строке заданы положительные числа N, M ≤ 40, следующие N строк содержат по M положительных чисел - проходимость данной клетки карты.
В следующей строке задано положительное число K ≤ 15 - количество промежуточных пунктов.
В следующих K строках записаны по 2 числа - 0 ≤ X_i < N, 0 ≤ Y_i < M - координаты i-го промежуточного пункта (X_{i }- номер строки (нумерация сверху вниз, начиная с нуля), Y_i - номер столбца (нумерация слева направо, начиная с нуля)).
В последней строки заданы 2 числа 0 < X < N, 0 < Y < M - координаты начала (и конца) движения.
Выходные данные
Выведите минимальное количество времени, которое потребуется роботу на прохождение.