РобоФест
Ви берете участь у змаганні з робототехніки "РобоФест". Ваш робот повинен обійти всі проміжні пункти та повернутися до початкової точки. У вас є карта місцевості, і ви хочете знайти найоптимальніший маршрут для вашого робота. Карта представлена у вигляді прямокутника розміром 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 — координати початку (і кінця) руху.
Вихідні дані
Виведіть мінімальний час, необхідний роботу для проходження маршруту.