Нужно ускорить/опитимизировать код

Воть-с задача, которую я тут пытаюсь решить:

La Cucaracha. Каждую полночь в квартире ученого Васи начинается ужас. Сотни ..., о нет! ТЫСЯ- ЧИ тараканов вылазят из каждой дырки к его обеденному столу, уничтожая все крошки и объедки! Вася ненавидит тараканов. Он очень долго думал и сделал Супер-ловушку, которая привлекает всех тараканов в большой зоне после активации. Он планирует ак- тивировать ловушку сегодня ночью. Но есть проблема. Эта очень эффективная ловушка с её очень большой зоной работы поглощает огромное количество энергии. Так что, Вася планирует минимизировать время работы этой ловушки. Он собрал информацию о всех местах, в которых живут тараканы. Также он заметил, что все тараканы двигаются толь- ко по линиям его скатерти с постоянной скоростью (мы можем предположить, что эта скорость равна 1, так что таракан расположенный в одной из секций, может за 1 едини- цу времени переместится на любую соседнюю секцию (по вертикали или горизонтали)). Вася решил активировать его ловушку в одной из секций. Когда ловушка активирована, все тараканы будут двигаться к секции, содержащей ловушку, так быстро, как только смогут. Поэтому в любой момент времени после активации тараканы двигаются к сек- ции, в которой находится ловушка, максимально уменьшая расстояние до неё. Если есть два пути с одинаковым расстоянием, то таракан выберет любой. Напишите программу для Васи, которая выбирает секцию, минимизирующую время, необходимое для уни- чтожения всех тараканов. Конечно, ваша программа будет считать, что скатерть будет плоскостью с декартовой системой координат и секции — точки с целыми координатами. Формат входного файла В первой строке входного файла содержится число мест, в которых живут тараканы М (1< М < 10000). Следующие М строк содержат 1 и у — координаты мест, в которых живут тараканы (целые числа не больше 10° по абсолютному значению). Формат выходного файла Вам необходимо вывести только два целых числа х и у, не превосходящие по модулю 10°, — координаты секции, которая минимизирует время работы. Если есть более одное решение — выведите любое из них.

Вот мой код:

def max_distance(trap_x, trap_y, coordinates):
    distance = 0
    for x, y in coordinates:
        distance = max(distance, abs(trap_x - x) + abs(trap_y - y))
    return distance
def main():
    M = int(input())
    coordinates = [tuple(map(int, input().split())) for _ in range(M)]
    x_min, _ = min(coordinates, key=lambda c: (c[0], c[1]))
    x_max, _ = max(coordinates, key=lambda c: (c[0], c[1]))
    _, y_min = min(coordinates, key=lambda c: (c[1], c[0]))
    _, y_max = max(coordinates, key=lambda c: (c[1], c[0]))
 
    min_time = float('inf')
    result_x, result_y = 0, 0
 
    for trap_x in range(x_min, x_max + 1):
        for trap_y in range(y_min, y_max + 1):
            cur_time = max_distance(trap_x, trap_y, coordinates)
            if cur_time < min_time:
                min_time = cur_time
                result_x, result_y = trap_x, trap_y
 
    print(result_x, result_y)




if __name__ == "__main__":
    main()

Но, он фейлится на тесте с 239 вводом координат. Как его можно ускорить?