Məsələlər
РобоФест
РобоФест
Вы участвуете в соревновании по робототехнике "РобоФест". Ваш робот должен обойти все промежуточные пункты и вернуться в начало. У вас имеется карта местности и вы хотите найти наиболее оптимальный маршрут для вашего робота. Карта имеет вид прямоугольника \textbf{N}×\textbf{M} клеток, в каждой клетке записано положительное число - время, которое будет затрачено на прохождение этой клетки роботом. Также у вас есть список координат промежуточных пунктов и точки начала.
\InputFile
В первой строке заданы положительные числа \textbf{N}, \textbf{M} ≤ \textbf{40}, следующие \textbf{N} строк содержат по \textbf{M} положительных чисел - проходимость данной клетки карты.
В следующей строке задано положительное число \textbf{K} ≤ \textbf{15} - количество промежуточных пунктов.
В следующих \textbf{K} строках записаны по \textbf{2} числа - \textbf{0} ≤ \textbf{X_i} < \textbf{N}, \textbf{0} ≤ \textbf{Y_i} < \textbf{M} - координаты \textbf{i}-го промежуточного пункта (\textbf{X_\{i \}}- номер строки (нумерация сверху вниз, начиная с нуля), \textbf{Y_i} - номер столбца (нумерация слева направо, начиная с нуля)).
В последней строки заданы \textbf{2} числа \textbf{0} < \textbf{X} < \textbf{N}, \textbf{0} < \textbf{Y} < \textbf{M} - координаты начала (и конца) движения.
\OutputFile
Выведите минимальное количество времени, которое потребуется роботу на прохождение.
Giriş verilənləri #1
5 1 24 83 41 48 41 1 2 0 3 0
Çıxış verilənləri #1
89