import heapq


def minRefuelStops_maxheap(
    target_distance: int, start_fuel: int, stations: list[list[int]]
) -> int:
    """Priority Queue, O(NlogN)

    For every loop:
        We add all reachable stop to priority queue.
        We pop out the largest gas from pq and refuel once.
        If we can't refuel => we can't go forward => return -1

    Complexity:
        n = len(stations)
            Time: O(nlogn)
            Space: O(n) for the heap

    Args:
        target_distance:
        start_fuel:
        stations: list of [distance, gallon] pairs, in sorted order of distance

    Returns: LEAST # of stops to destination OR -1 if not possible

    Examples:
        >>> stations = [[10,60],[20,30],[30,30],[60,40]]
        >>> minRefuelStops_maxheap(target_distance=100, start_fuel=10, stations=stations)
        2
        >>> minRefuelStops_maxheap(target_distance=100, start_fuel=1, stations=stations)
        -1
        >>> minRefuelStops_maxheap(target_distance=1, start_fuel=1, stations=[])
        0
        >>> stations = [[10,10],[20,10],[30,30],[60,40]]
        >>> minRefuelStops_maxheap(target_distance=100, start_fuel=10, stations=stations)
        4

    """
    ## Initialize

    # vars
    next_station_idx = 0
    curr_fuel = start_fuel

    # DS's/res
    priority_queue = []  # maxheap of fuel amounts from reachable station
    num_stops = 0

    while curr_fuel < target_distance:
        ## ADD currently reachable stations
        while (
            next_station_idx < len(stations)
            and stations[next_station_idx][0] <= curr_fuel
        ):
            station_fuel = stations[next_station_idx][1]
            # make a maxheap by negating value
            heapq.heappush(priority_queue, -station_fuel)
            next_station_idx += 1

        ## HANDLE EMPTY
        # no reachable stations => no gas to travel further => FAIL
        if not priority_queue:
            return -1

        ## VISIT reachable station
        # Add all fuel from the MAX(station_fuel) reachable station;
        # Remove station from priority_queue
        #   Note: adding to curr_fuel implicitly takes distance into account
        curr_fuel += -heapq.heappop(priority_queue)
        num_stops += 1  # increment visited stations count

    return num_stops