class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        arr = []
        for x, y in points:
            if x == 0: arr.append(y)
            elif y == side: arr.append(side + x)
            elif x == side: arr.append(3 * side - y)
            else: arr.append(4 * side - x)
        arr.sort()

        def check(limit: int) -> bool:
            perimeter = side * 4
            for start in arr:
                end = start + perimeter - limit
                cur = start
                for _ in range(k - 1):
                    idx = bisect_left(arr, cur + limit)
                    if idx == len(arr) or arr[idx] > end:
                        cur = -1
                        break
                    cur = arr[idx]
                if cur != -1: return True
            return False

        low, high, ans = 1, side, 0
        while low <= high:
            mid = (low + high) // 2
            if check(mid):
                ans = mid
                low = mid + 1
            else: high = mid - 1
        return ans