Карел - робот, который живет в прямоугольной системе координат, где каждое место в множестве обозначено целочисленными координатами (x и y). Ваша задача заключается в разработке программы, которая поможет Карелу собрать ряд пейджеров, которые находятся в его мире. Для этого необходимо направить Карела к месту, где источник каждого из звуковых сигналов находится. Ваша задача написать компьютерную программу, которая находит длину кратчайшего пути, необходимого Карелу, чтобы собрать все пейджеры и вернуться обратно в исходное положение.
Карел может двигаться только вдоль осей x и y, но не по диагонали. Переход от одной позиции (i, j) в соседнюю позицию (i, j+1), (i, j-1), (i-1, j) или (i+1, j) имеет единичную стоимость.
Можно предположить, что мир Карела никогда не бывает больше квадрата 20×20, и что никогда не будет задано собрать более 10 пейджеров. Каждая координата будет предоставлена в виде пары (x, y), где каждое значение будет в пределах 1 по размеру данного направления системы координат.
Сначала идёт строка, содержащая количество сценариев, в которых вас просят помочь Карелу. В начале каждого сценария сначала идёт строка, содержащая размер мира. Она содержит два целых числа х и у. Далее идёт строка, содержащая координаты исходного положения Карла. В следующей строке задано одно число: количество пейджеров – источников звукового сигнала. Каждый источник звукового сигнала задан далее в отдельной строке, содержащей два числа - координаты каждого звукового сигнала.
Для каждого сценария в отдельной строке выведите искомый результат - минимальное расстояние, которое должен пройти Карел, чтобы собрать все пейджеры и вернуться в исходное положение.