<p>You have <code>n</code> robots. You are given two <strong>0-indexed</strong> integer arrays, <code>chargeTimes</code> and <code>runningCosts</code>, both of length <code>n</code>. The <code>i<sup>th</sup></code> robot costs <code>chargeTimes[i]</code> units to charge and costs <code>runningCosts[i]</code> units to run. You are also given an integer <code>budget</code>.</p>

<p>The <strong>total cost</strong> of running <code>k</code> chosen robots is equal to <code>max(chargeTimes) + k * sum(runningCosts)</code>, where <code>max(chargeTimes)</code> is the largest charge cost among the <code>k</code> robots and <code>sum(runningCosts)</code> is the sum of running costs among the <code>k</code> robots.</p>

<p>Return<em> the <strong>maximum</strong> number of <strong>consecutive</strong> robots you can run such that the total cost <strong>does not</strong> exceed </em><code>budget</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
<strong>Output:</strong> 3
<strong>Explanation:</strong> 
It is possible to run all individual and consecutive pairs of robots within budget.
To obtain answer 3, consider the first 3 robots. The total cost will be max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 which is less than 25.
It can be shown that it is not possible to run more than 3 consecutive robots within budget, so we return 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
<strong>Output:</strong> 0
<strong>Explanation:</strong> No robot can be run that does not exceed the budget, so we return 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>chargeTimes.length == runningCosts.length == n</code></li>
	<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= chargeTimes[i], runningCosts[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= budget &lt;= 10<sup>15</sup></code></li>
</ul>

class Solution:
    def maximumRobots(self, times: List[int], costs: List[int], budget: int) -> int:
        from sortedcontainers import SortedList
        s = SortedList()
        res=0
        j=0
        cur=0
        for i in range(len(times)):
            cur += costs[i]
            s.add(times[i])
            if s[-1] + (i-j+1)*cur > budget:
                s.remove(times[j])
                cur-=costs[j]
                j+=1
            res = max(res, i-j+1)
        return res

        # cur = j=0
        # s = SortedList()
        # res=0

        # for i in range(len(times)):
        #     cur += costs[i]
        #     s.add(times[i])
        #     if s[-1] + cur*(i-j+1) > budget:
        #         s.remove(times[j])
        #         cur -= costs[j]
        #         j+=1
        #     res = max(res,i-j+1)
        # return res

        # cur = i = 0
        # n = len(times)
        # d = deque()
        # for j in range(n):
        #     cur += costs[j]
        #     while d and times[d[-1]] <= times[j]:
        #         d.pop()
        #     d.append(j)
        #     if times[d[0]] + (j - i + 1) * cur > budget:
        #         if d[0] == i:
        #             d.popleft()
        #         cur -= costs[i]
        #         i += 1
        # return n - i




        


        # def remove_stale(pq, j):
        #     while pq and pq[0][1] <= j: heappop(pq)
        #     return -pq[0][0] if pq else 0
        # ans, s, j, pq = 0, 0, -1, []
        # for i in range(len(runningCosts)):
        #     s += runningCosts[i]
        #     heappush(pq, (-chargeTimes[i], i))
        #     while s * (i - j) + remove_stale(pq, j) > budget:
        #         j += 1
        #         s -= runningCosts[j]
        #     ans = max(ans, i - j)
        # return ans

        # def remove_stale(pq, j):
        #     while pq and pq[0][1] <= j: heappop(pq)
        #     return -pq[0][0] if pq else 0
        # for i in range(len(runningCosts)):
        #     s += runningCosts[i]
        #     heappush(pq, (-chargeTimes[i], i))
        #     while s*(i-j) + remove(pq, j) > budget:
        #         j+=1
        #         s-=runningCosts[j]
        #     ans = max(ans, i-j)
        # return ans
1403