A car travels from a starting position to a destination which is target miles east of the starting position.
Along the way, there are gas stations.  Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.
The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it.  It uses 1 liter of gas per 1 mile that it drives.
When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.
What is the least number of refueling stops the car must make in order to reach its destination?  If it cannot reach the destination, return -1.
Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there.  If the car reaches the destination with 0 fuel left, it is still considered to have arrived.
 

Example 1:
Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.


Example 2:
Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can't reach the target (or even the first gas station).


Example 3:
Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: 
We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel.  We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas.  We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

 
Note:

1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

Difficulty: interview

Starter code:

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target: return 0
        heap = [] #record the reachable gas for now
        stop = 0 #total stops
        dist = startFuel #reachable distance
        for d, g in stations:
            if dist >= target: #if reach target, return
                return stop
            while heap and dist < d: #make sure we can reach current station by make minimum stops
                gas = heapq.heappop(heap)
                dist += -gas
                stop += 1
            if dist < d: #if not reachable, return -1
                return -1
            heapq.heappush(heap, (-g)) #add current gas to heap for future stop
        if dist >= target:
                return stop
        while heap: #add the rest gas in heap from max to min to reach the target
            g = heapq.heappop(heap)
            stop += 1
            dist += -g
            if dist >= target:
                return stop
        return -1
        
                
                
            
        
                


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target:
            return 0
        if not stations:
            return -1

        fdelta = startFuel-stations[0][0]
        if fdelta < 0:
            return -1

        curr = [fdelta + stations[0][1], fdelta]

        for i, sta in enumerate(stations[1:]):
            treck = sta[0] - stations[i][0]
            leftover = curr[0]-treck
            if leftover < 0:
                return -1
            nex = [leftover + sta[1], leftover]
            for j, f in enumerate(curr[1:]):
                leftover = curr[j+1] - treck
                if leftover < 0:
                    break
                else:
                    nex[-1] = max(nex[-1], leftover+sta[1])
                    nex.append(leftover)

            curr = nex

        leftover = target - stations[-1][0]

        while curr and curr[-1] < leftover:
            curr.pop()

        return len(stations) - len(curr) + 1 if curr else -1

import heapq


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        stops = 0
        max_gas_heap = []
        can_drive_to = startFuel
        i = 0
        while can_drive_to < target:
            # push stations to heap
            while i < len(stations) and stations[i][0] <= can_drive_to:
                heapq.heappush(max_gas_heap, -stations[i][1])
                i += 1
            
            if not max_gas_heap:
                return -1
            can_drive_to -= heapq.heappop(max_gas_heap)
            stops += 1

        return stops


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target:
            return 0
        n = len(stations)
        dp = [0]*(n+1)
        dp[0] = startFuel
        
        
        for i in range(1, n+1):
            for j in range(i, 0, -1):
                if dp[j-1] >= stations[i-1][0]:
                    # use station i-1
                    dp[j] = max(dp[j], dp[j-1] + stations[i-1][1])
                
        for i in range(1, n+1):
            if dp[i] >= target:
                return i
        return -1

import heapq
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        point=0
        level=0
        gas=startFuel
        if gas>=target:
            return level
        heap=[]
        stations.append([target+1,float('inf')])
        for pos,gas_add in stations:
            if gas>=pos:
                heapq.heappush(heap,-gas_add)
            else:
                while heap:
                    gasmin=heapq.heappop(heap)
                    gas-=gasmin
                    level+=1
                    if gas>=target:
                        return level
                    if gas>=pos:
                        heapq.heappush(heap,-gas_add)
                        break
        return -1
                
                
        
       
            


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target:
            return 0
        if startFuel < target and not stations:
            return -1
        dp = [startFuel] + [0] * len(stations)
        for i, val in enumerate(stations):
            for t in range(i, -1, -1):
                if dp[t] >= val[0]:
                    dp[t+1] = max(dp[t+1], dp[t] + val[1])
        for i, d in enumerate(dp):
            if d >= target:
                return i
        return -1

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
#         if startFuel >= target:
#             return 0

#         @lru_cache(maxsize=None)
#         def helper(startIdx, litre, target):
#             if litre >= target:
#                 return 0

#             result = float('inf')
#             for idx in range(startIdx + 1, len(stations)):
#                 if startIdx == -1:
#                     n_miles = stations[idx][0]
#                 else:    
#                     n_miles = stations[idx][0] - stations[startIdx][0]

#                 remain = litre - n_miles
#                 if remain >= 0:
#                     result = min(result, 1 + helper(idx, remain + stations[idx][1], target - n_miles))
#             return result

#         result = helper(-1, startFuel, target)
#         return -1 if result == float('inf') else result

#-----------------------------------------------------------------------------

#         if startFuel >= target:
#             return 0

#         heap = []

#         idx = n_stations = 0
#         maxDistance = startFuel

#         while maxDistance < target:
#             while idx < len(stations) and stations[idx][0] <=maxDistance:
#                 heapq.heappush(heap, -stations[idx][1])
#                 idx += 1

#             if not heap:
#                 return -1

#             maxDistance += (-heapq.heappop(heap))
#             n_stations += 1
#         return n_stations

#-----------------------------------------------------------------------------

#         if startFuel >= target:
#             return 0

#         length = len(stations)
#         dp = [[0] * (1 + length) for _ in range(1 + length)]
#         for i in range(1 + length):
#             dp[i][0] = startFuel

#         result = float('inf')
#         for i in range(1 + length):
#             for j in range(1, i + 1):
#                 if j <= i - 1:
#                     dp[i][j] = max(dp[i][j], dp[i - 1][j])

#                 if dp[i - 1][j - 1] >= stations[i - 1][0]:
#                     dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + stations[i - 1][1])

#                 if dp[i][j] >= target:
#                     result = min(result, j)
#         return -1 if result == float('inf') else result

#-----------------------------------------------------------------------------
        
        if startFuel >= target:
            return 0
        
        length = len(stations)
        dp = [startFuel] + [0] * length
        result = float('inf')
        for i in range(1 + length):
            for j in range(i, 0, -1):
                if dp[j - 1] >= stations[i - 1][0]:
                    dp[j] = max(dp[j], dp[j - 1] + stations[i - 1][1])

                if dp[j] >= target:
                    result = min(result, j)
        return -1 if result == float('inf') else result

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target : return 0
        
        pq = []
        minStops = i = 0
        curr = startFuel
        
        while curr < target:
            while i < len(stations) and curr >= stations[i][0]:
                heapq.heappush(pq, -stations[i][1])
                i += 1
            if not pq: return -1
            curr += -heapq.heappop(pq)
            minStops +=1
        return minStops


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        
        if startFuel >= target:
            return 0
        
        from heapq import heapify, heappop, heappush
        
        dis = startFuel
        heap = []
        stations = stations[::-1] 
        while stations and stations[-1][0] <= dis:
            s = stations.pop()
            heap.append((-s[1], s[0]))
            
        heapify(heap)
        
        
        stops = 0
        
        while heap:
            
            most_fuel = heappop(heap)
            stops += 1
            dis += (-most_fuel[0])
            if dis >= target:
                return stops
            while stations and stations[-1][0] <= dis:
                s = stations.pop()
                heappush(heap, (-s[1], s[0]))
            
        return -1
            
            
        


class Solution:
    def minRefuelStops(self, target, startFuel, stations):
        stations.append([target, 0])
        stations.sort(reverse=True)
        curr, tank = 0, startFuel
        ans = 0
        refuels = []
        while curr + tank < target:
            pos, gas = stations.pop()
            if pos <= curr+tank:
                heapq.heappush(refuels, -gas)
            else:
                curr += tank
                tank = 0
                while curr+tank < pos and refuels:
                    ans += 1
                    tank -= heapq.heappop(refuels)
                if curr+tank < pos:
                    return -1
                heapq.heappush(refuels, -gas)
        return ans

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        
        q=[]
        extent = startFuel
        
        ans = 0
        for i in range(len(stations)):
            if extent>=target:
                return ans
            
            loc, fuel = stations[i]
            while q and loc>extent :
                extent += -heapq.heappop(q)
                ans+=1
            
            if loc>extent:
                return -1
            
            heapq.heappush(q, -fuel)
            
        while q and extent<target:
            extent+=-heapq.heappop(q)
            ans+=1
        
        if extent>=target:
            return ans
        else:
            return -1
                
                
                
                
            


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        
        q=[]
        extent = startFuel
        
        ans = 0
        for i in range(len(stations)):
            if extent>=target:
                return ans
            
            loc, fuel = stations[i]
            print((i, loc, extent))
            while q and loc>extent :
                extent += -heapq.heappop(q)
                ans+=1
            
            if loc>extent:
                return -1
            
            heapq.heappush(q, -fuel)
            
        while q and extent<target:
            extent+=-heapq.heappop(q)
            ans+=1
        
        if extent>=target:
            return ans
        else:
            return -1
                
                
                
                
            


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        pq = []
        idx = 0 
        cur = startFuel
        res = 0
        while cur < target: 
            while idx < len(stations) and cur >= stations[idx][0]:
                heapq.heappush(pq, -stations[idx][1])
                idx += 1
            if not pq: return -1 
            cur -= heapq.heappop(pq)
            res += 1
        return res


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target:
            return 0
        
        if not stations:
            return -1
        
        steps = 0
        i = 0
        pq = []
        
        while startFuel < target:
            while i < len(stations) and stations[i][0] <= startFuel:
                heapq.heappush(pq, -stations[i][1])
                i += 1
            
            if not pq:
                return -1
            else:
                startFuel -= heapq.heappop(pq)
                steps += 1
            
                    
        return steps

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        heap = []
        queue = deque()
        i = 0
        num_stations = 0
        
        while startFuel < target:
            while i < len(stations) and startFuel >= stations[i][0]:
                heapq.heappush(heap, (-stations[i][1]))
                i += 1
            
            if not heap:
                return -1
            
            next_fuel = heapq.heappop(heap)
            startFuel -= next_fuel
            num_stations += 1
        
        return num_stations

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target:
            return 0

        N = len(stations)

        # We will try different number of stops. Initial state num_stops=0.
        # memo[num_stations] = max_mile we can reach if only available
        # first num_stations, and we make exactly num_stops

        prev_memo = [startFuel] * (N + 1)

        for num_stops in range(1, N + 1):
            memo = [-1] * (N + 1)

            a = -1
            for num_stations in range(num_stops, N + 1):
                station_mile, station_fuel = stations[num_stations - 1]
                # a = memo[num_stations - 1]
                # Optimization: a is available from previous loop,
                # so don't need to access it from memo[]
                b = prev_memo[num_stations - 1]
                if b >= station_mile:  # Check if we can reach this station
                    a = max(a, b + station_fuel)
                if a != -1:
                    memo[num_stations] = a

            # if memo[N] >= target:
            if a >= target:
                return num_stops

            prev_memo = memo

        return -1

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target:
            return 0

        N = len(stations)

        # We will try different number of stops. Initial state num_stops=0.
        # memo[num_stations] = max_mile we can reach if only available
        # first num_stations, and we make exactly num_stops

        prev_memo = [startFuel] * (N + 1)

        for num_stops in range(1, N + 1):
            memo = [-1] * (N + 1)

            a = -1
            for num_stations in range(num_stops, N + 1):
                station_mile, station_fuel = stations[num_stations - 1]
                # a = memo[num_stations - 1]
                # Optimization: a is available from previous loop,
                # so don't need to access it from memo[]
                b = prev_memo[num_stations - 1]
                if b >= station_mile:  # Check if we can reach this station
                    a = max(a, b + station_fuel)
                memo[num_stations] = a

            # if memo[N] >= target:
            if a >= target:
                return num_stops

            prev_memo = memo

        return -1

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel>=target:
            return 0
        stations.sort(reverse=True)
        fuel=startFuel
        heap=[]
        out=0
        while stations:
            while stations and fuel>=stations[-1][0]:
                t,val=stations.pop()
                if t>=target:
                    return out
                heapq.heappush(heap,-val)
            if heap:
                fuel-=heapq.heappop(heap)
                out+=1
                if fuel>=target:
                    return out
            else:
                break
        while heap and fuel<target:
            fuel-=heapq.heappop(heap)
            out+=1
        if fuel<target:
            return -1
        return out

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target:
            return 0

        N = len(stations)

        # We will try different number of stops. Initial state num_stops=0.
        # memo[num_stations] = max_mile we can reach if only available
        # first num_stations, and we make exactly num_stops

        prev_memo = [startFuel] * (N + 1)

        for num_stops in range(1, N + 1):
            memo = [-1] * (N + 1)

            a = -1
            for num_stations in range(num_stops, N + 1):
                station_mile, station_fuel = stations[num_stations - 1]
                # a = memo[num_stations - 1]
                # Optimization: a is available from previous loop,
                # so don't need to access it from memo[]
                b = prev_memo[num_stations - 1]
                if b >= station_mile:  # Check if we can reach this station
                    b += station_fuel
                    a = max(a, b)
                if a != -1:
                    memo[num_stations] = a

            # if memo[N] >= target:
            if a >= target:
                return num_stops

            prev_memo = memo

        return -1

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if target <= startFuel:
            return 0
        dpRefuels = [-1] * len(stations)
        for i in range(len(stations)):
            if stations[i][0] <= startFuel:
                dpRefuels[i] = stations[i][1] + startFuel
                if dpRefuels[i] >= target:
                    return 1
            
        for k in range(1, len(stations)):
            # use k stations to reach target
            maxPrevFuel = dpRefuels[k-1]
            for i in range(k, len(stations)):
                # the i-th station would be the k-th refuel at each iteration
                temp = max(maxPrevFuel, dpRefuels[i])
                if maxPrevFuel >= stations[i][0]:
                    dpRefuels[i] = maxPrevFuel + stations[i][1]
                if dpRefuels[i] >= target:
                    return k + 1
                maxPrevFuel = temp
                
        return -1


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        fuel = startFuel
        del startFuel
        i = 0
        while target > fuel:
            target -= fuel
            stations = [[dist-fuel, gas] for dist, gas in stations]
            try:
                j, fuel = max([[j, gas]
                               for j, (dist, gas) 
                               in enumerate(stations) 
                               if dist <= 0], 
                               key=lambda stop: stop[1])
            except ValueError:
                return -1
            if fuel == 0:
                return -1
            stations[j][1] = 0
            i += 1
        return i

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if target <= startFuel:
            return 0
        dpRefuels = [[-1] * len(stations) for _ in range(len(stations))]
        for i in range(len(stations)):
            if stations[i][0] <= startFuel:
                dpRefuels[0][i] = stations[i][1] + startFuel
                if dpRefuels[0][i] >= target:
                    return 1
            
        for k in range(1, len(stations)):
            # use k stations to reach target
            maxPrevFuel = dpRefuels[k-1][k-1]
            for i in range(k, len(stations)):
                # the i-th station would be the k-th refuel at each iteration
                if maxPrevFuel >= stations[i][0]:
                    dpRefuels[k][i] = maxPrevFuel + stations[i][1]
                if dpRefuels[k][i] >= target:
                    return k + 1
                maxPrevFuel = max(maxPrevFuel, dpRefuels[k-1][i])
        return -1


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target: return 0
        if not stations: return -1
        data = []

        for k in range(len(stations)):
            data.append([stations[k][0]-(stations[k-1][0] if k > 0 else 0), stations[k][1]])
        data.append([target-stations[-1][0],0])

        # data is a list of [how far you have to go to reach station x from previous station, how much gas you get at station x]
        # we add a \"station\" at the target with 0 gas... we want to see if we can reach this spot
        
        # let's check if we made all stops, we could make it
        tot = startFuel
        for dist,gas in data:
            tot -= dist            
            if tot < 0: return -1
            tot += gas
        
        N = len(data)
        
        # maxFuel represents how much fuel you could have at this station 
        maxFuel = [float('-inf')] * N  
        
        # let's start with 0 stops
        tot = startFuel
        for k in range(N):
            dist,_ = data[k]
            tot -= dist
            if tot < 0: break            
            maxFuel[k] = tot
            
        #print('after 0 stops',maxFuel)
            
        # let's do 1 stop separately as well
        nextMaxFuel = [float('-inf')] * N
        nextMaxFuel[0] = maxFuel[0] + data[0][1]
        for k in range(1,N):
            dist,gas = data[k]
            if maxFuel[k] != float('-inf'):
                nextMaxFuel[k] = maxFuel[k]+gas
            if nextMaxFuel[k-1] >= dist:
                nextMaxFuel[k] = max(nextMaxFuel[k], nextMaxFuel[k-1]-dist)
            if nextMaxFuel[k] == float('-inf'):
                break
        
        if nextMaxFuel[-1] >= 0: return 1
        
        maxFuel = nextMaxFuel
        
        #print('after 1 stop',maxFuel)

        for nStops in range(2, N+1):
            nextMaxFuel = [float('-inf')] * N            
            for k in range(nStops-1, N):
                dist,gas = data[k]
                if maxFuel[k-1] != float('-inf') and maxFuel[k-1] >= dist: # i.e., we could make it to the station with nStops-1
                    nextMaxFuel[k] = maxFuel[k-1] - dist + gas
                if nextMaxFuel[k-1] >= dist:
                    nextMaxFuel[k] = max(nextMaxFuel[k], nextMaxFuel[k-1]-dist) # i.e., don't stop at this station, use prior result
                if nextMaxFuel[k] == float('-inf'):
                    break # we won't be able to get to later stations either
            #print('after',nStops,'stops',nextMaxFuel)
            if nextMaxFuel[-1] >= 0: return nStops
            maxFuel = nextMaxFuel
           
        return -1
            


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        stations = [[0,startFuel]] + sorted(stations)
        n = len(stations)        
        reach = [-float('inf')]*n
        reach[0] = startFuel
        st = [startFuel]*n
        flag = True
        cnt = 0
        if target <= startFuel:
            return 0
        while flag:
            flag = False
            cnt += 1
            for i in range(1,len(reach))[::-1]:
                p, g = stations[i]
                st.pop()
                if p <= st[-1] and st[-1] + g > reach[i]:
                    reach[i] = st[-1] + g
                    flag = True
                    if reach[i] >= target:
                        return cnt
            for i in range(1,len(reach)):
                st.append(max(st[-1],reach[i]))
            
        return -1

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        # dp[i]: (a, b). a-> the longest distance a car can travel with i refuels
        #                b-> the location(distance) of fuels already used
       
        dp=[[startFuel,[]]]
        for i in range(len(stations)):
            if dp[-1][0]>=target:
                break
            #print(\" \")
            #print(dp)
            usedStations=dp[-1][1]
            #print(usedStations)
            # reachable stations
            usable_stations=[s for s in stations if s[0]<=dp[-1][0] and s[0] not in usedStations]
            usable_stations.sort(key=lambda x:x[1])
            if len(usable_stations)==0:
                break
            #print(usable_stations)
            dp.append([dp[-1][0]+usable_stations[-1][1], dp[-1][1].copy()])
            dp[-1][1].append(usable_stations[-1][0])

        return len(dp)-1 if dp[-1][0]>=target else -1
        
            
            
        


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        n = len(stations)
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        
        for row in dp:
            row[0] = startFuel
    
        if startFuel >= target: return 0
        for refuels in range(1, n+1):
            for stas in range(refuels, n+1):
                station = stations[stas-1]
                dp[stas][refuels] = dp[stas-1][refuels]
                if dp[stas-1][refuels-1] >= station[0]:
                    dp[stas][refuels] = max(station[1] + dp[stas-1][refuels-1], dp[stas][refuels])

            if dp[n][refuels] >= target: return refuels
            
        return -1
    
    
    
    
    
#             for refue in range(1, n + 1):
#             for station in range(1, n + 1):
#                 dp[station][refue] = dp[station - 1][refue]
#                 if dp[station - 1][refue - 1] >= stations[station - 1][0]:
#                     dp[station][refue] = max(dp[station - 1][refue - 1] + stations[station - 1][1], dp[station][refue])
                
#             if dp[n][refue] >= target:
#                 return refue
        
#         return -1



class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        return self.dp(target, startFuel, stations)
    
    def dp(self, target, startFuel, stations):
        if startFuel >= target:
            return 0
        if not stations:
            return -1
        
        # A[t][i] = max distance using first i stations and stop t times (t<=i)
        # A[t][i] = max(
        #    A[t][i-1],
        #    A[t-1][i-1] + stations[i-1][1] if A[t-1][i-1] >= stations[i-1][0]
        
        n = len(stations)
        A = [[0] * (n+1) for _ in range(n+1)]
        
        for i in range(n+1):
            A[0][i] = startFuel
        
        for t in range(1, n+1):
            for i in range(1, n+1):
                if t <= i:
                    A[t][i] = A[t][i-1]
                    if A[t-1][i-1] >= stations[i-1][0]:
                        A[t][i] = max(A[t][i], A[t-1][i-1] + stations[i-1][1])
            if A[t][-1] >= target:
                return t
            
        return -1
    
    
    def rec1(self, target, startFuel, stations, position, station_idx_start):
        if position >= target or startFuel >= (target - position):
            #print(target, startFuel, stations, position)
            return 0
        else:
            candidates = []
            for idx in range(station_idx_start, len(stations)):
                p, f = stations[idx]
                d = p - position
                valid = d > 0 and startFuel - d >= 0
                if valid:
                    candidates.append(1 + self.rec(
                        target, 
                        startFuel - d + f, 
                        stations, 
                        p,
                        station_idx_start + 1))
                if startFuel - d < 0:
                    break
            
            if not candidates:
                return float('inf')
            else:
                return min(candidates)

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        n = len(stations)
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        
        for row in dp:
            row[0] = startFuel
    
        if startFuel >= target: return 0
        
        for refuels in range(1, n+1):
            for stas in range(1, n+1):
                station = stations[stas-1]
                dp[stas][refuels] = dp[stas-1][refuels]
                if dp[stas-1][refuels-1] >= station[0]:
                    dp[stas][refuels] = max(station[1] + dp[stas-1][refuels-1], dp[stas][refuels])

            if dp[n][refuels] >= target: return refuels
            
        return -1
    
    
    
    
    
#             for refue in range(1, n + 1):
#             for station in range(1, n + 1):
#                 dp[station][refue] = dp[station - 1][refue]
#                 if dp[station - 1][refue - 1] >= stations[station - 1][0]:
#                     dp[station][refue] = max(dp[station - 1][refue - 1] + stations[station - 1][1], dp[station][refue])
                
#             if dp[n][refue] >= target:
#                 return refue
        
#         return -1


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        # f[i,j], the maximum full one can have, using j stations, stop at station i, 
        # f[i,j] = f[i],  j implied by iteration
        if target<=startFuel:
            return 0
        
        stations=[[0, startFuel]]+stations
        print(stations)
        N=len(stations)
        f = [startFuel-stations[i][0] for i in range(N)]
        f[0]=startFuel
        
        
        print(f)
        for j in range(N):
            g = [-1]*(N)
            g[0]=f[0]
            for i in range(N-1,0,-1):
                if f[i-1]-(stations[i][0]-stations[i-1][0])>=0:
                    g[i]=f[i-1]+stations[i][1]-(stations[i][0]-stations[i-1][0])
                
            for i in range(1,N):
                g[i]=max(g[i-1]-(stations[i][0]-stations[i-1][0]), g[i])
            
            f = g
            if f[-1]>=(target-stations[-1][0]):
                return j+1
            
        return -1
                
            


class Solution:
    def minRefuelStops(self, t: int, f: int, st: List[List[int]]) -> int:
        if f >= t: return 0
        if st == []: return -1
        if f < st[0][0]: return -1
        li,li1 = [],[]
        for i,j in st:
            li.append(i)
            li1.append(j)
        count = 0
        while f <  t:
            s,tur = 0,[]            
            for i in li:
                if f >= i: 
                    s = li.index(i)
                    tur.append(True)
                else: tur.append(False)
            print(tur)
            if all(i == False for i in tur): return -1
            f += max(li1[0:s+1])
            li.pop(li1.index(max(li1[0:s+1])))
            li1.remove(max(li1[0:s+1]))
            count +=1
        return count

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if target<=startFuel:
            return 0
        
        dp=[[0 for _ in range(len(stations)+1)] for _ in range(len(stations)+1)]
        for i in range(len(stations)+1):
            dp[i][0]=startFuel
            
        for i in range(1, len(stations)+1):
            for j in range(1, len(stations)+1):
                dp[j][i]=dp[j-1][i]
                
                if dp[j-1][i-1]>=stations[j-1][0]:
                    dp[j][i]=max(dp[j][i], dp[j-1][i-1]+stations[j-1][1])
                
            if dp[j][i]>=target:
                return i
            
        return -1

from functools import lru_cache


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        
        @lru_cache(None)
        def farthest_of_first_n_with_stops(n, stops):
            if n == 0 or stops == 0:
                return startFuel

            dont_refuel_now = farthest_of_first_n_with_stops(n - 1, stops)
            refuel_now = farthest_of_first_n_with_stops(n - 1, stops - 1)
            x, fuel = stations[n - 1]
            if refuel_now < x:  # can't reach stations[n - 1]
                return dont_refuel_now
            else:
                return max(dont_refuel_now, fuel + refuel_now)

        for stops in range(len(stations) + 1):
            # print(farthest_of_first_n_with_stops(len(stations), stops))
            if farthest_of_first_n_with_stops(len(stations), stops) >= target:
                return stops

        return -1


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        @lru_cache(maxsize=None)
        def solve(s: int, stops: int) -> int:
            if stops == 0 or s < 0:
                return startFuel
            
            return max(solve(s - 1, stops), (sub + stations[s][1]) if (sub := solve(s - 1, stops - 1)) >= stations[s][0] else 0)
        
        for i in range(len(stations) + 1):
            if solve(len(stations) - 1, i) >= target:
                return i
        
        return -1

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target:
            return 0
        if not stations:
            return -1
        import heapq
        queue = [-f for i,f in stations if i <= startFuel]
        heapq.heapify(queue)
        fuel = startFuel
        start = max([i for i in range(len(stations)) if stations[i][0] <= startFuel] + [-1]) + 1
        result = 0
        while queue and fuel < target:
            fuel -= heapq.heappop(queue)
            result += 1
            while start < len(stations) and fuel >= stations[start][0]:
                heapq.heappush(queue, -stations[start][1])
                start += 1
        return result if fuel >= target else -1

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if target==startFuel:
            return 0
        
        stations=[startFuel]+stations
        dp=[0]*len(stations)
        dp[0]=(startFuel)
        for i in range(1, len(stations)):
            j=i-1
            while j>=0:
                totalFuel=dp[j]+stations[i][1] 
                if dp[j] >=stations[i][0] and totalFuel>=dp[j+1]:
                    dp[j+1]=(totalFuel)
                j-=1
        # print(dp)
        for i,fuel in enumerate(dp):
            if fuel>=target:return i
        return -1

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if target <= startFuel:
            return 0
        
        if not stations:
            return -1
        
        dp = [startFuel]
        stops = 0
        lastd = 0
        for d, fuel in stations:
            for i in range(stops, len(dp)):
                dp[i] -= d - lastd
                if dp[i] < 0:
                    stops = i + 1
            
            if stops == len(dp):
                return -1
            
            dp.append(dp[-1] + fuel)
            for i in range(len(dp) - 2, stops, -1):
                dp[i] = max(dp[i], dp[i - 1] + fuel)
                
            if dp[stops] >= target - d:
                return stops
            
            lastd = d
        
        while stops < len(dp):
            if dp[stops] >= target - lastd:
                return stops
            stops += 1
        
        return -1


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target: return 0
        heap = []
        for d, g in stations:
            heapq.heappush(heap, (-g, d))
        dist = startFuel
        stop = 0
        dist = startFuel
        tmp = []
        while heap:
            g, d = heapq.heappop(heap)
            if d <= dist:
                dist += -g
                if dist >= target:
                    return stop + 1
                for el in tmp:
                    heapq.heappush(heap, el)
                tmp = []
                stop += 1
            else:
                tmp.append((g, d))
        return -1
        
                
                
            
        
                


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        stations = [[0,0]] + stations
        heap = [(0, 0, -startFuel)]
        seen = {}
        while heap:
            stop, pos, fuel = heappop(heap)
            pos = -pos
            fuel = -fuel
            
            if pos in seen and seen[pos] >= fuel:
                continue
            seen[pos] = fuel
            
            if stations[pos][0] + fuel >= target:
                return stop
            
            if pos+1 < len(stations) and fuel >= stations[pos+1][0] - stations[pos][0]:
                new_fuel = fuel - (stations[pos+1][0] - stations[pos][0])
                heappush(heap, (stop+1, -(pos+1), -(new_fuel + stations[pos+1][1])))
                heappush(heap, (stop, -(pos+1), -new_fuel))
        return -1