"""
p88 — IPO (LC 502)

INVARIANT (two-heap): min-heap-by-capital holds unaffordable projects; max-heap-
  by-profit holds currently-affordable projects. Each round: promote affordable
  projects from min to max; pop max profit; add to capital.

INVARIANT (sort variant): sort projects by capital ascending; walk pointer
  through sorted list; push profit to max-heap whenever capital[ptr] <= w.
"""
from __future__ import annotations

import heapq
import random
from itertools import combinations
from typing import List


def find_maximized_capital_two_heap(k: int, w: int, profits: List[int], capital: List[int]) -> int:
    """Two heaps. O((n + k) log n)."""
    n = len(profits)
    min_capital_heap: List[tuple[int, int]] = [(capital[i], profits[i]) for i in range(n)]
    heapq.heapify(min_capital_heap)
    max_profit_heap: List[int] = []  # negated profits

    for _ in range(k):
        # Promote everything affordable.
        while min_capital_heap and min_capital_heap[0][0] <= w:
            _, p = heapq.heappop(min_capital_heap)
            heapq.heappush(max_profit_heap, -p)
        if not max_profit_heap:
            break
        w += -heapq.heappop(max_profit_heap)
    return w


def find_maximized_capital_sort(k: int, w: int, profits: List[int], capital: List[int]) -> int:
    """Sort by capital + single max-heap. O((n + k) log n), simpler constants."""
    n = len(profits)
    projects = sorted(zip(capital, profits))  # by capital asc
    max_heap: List[int] = []
    ptr = 0
    for _ in range(k):
        while ptr < n and projects[ptr][0] <= w:
            heapq.heappush(max_heap, -projects[ptr][1])
            ptr += 1
        if not max_heap:
            break
        w += -heapq.heappop(max_heap)
    return w


def find_maximized_capital_brute(k: int, w: int, profits: List[int], capital: List[int]) -> int:
    """Oracle: try all subsets of size <= k; for each, try every order; check feasibility."""
    n = len(profits)
    best = w
    for size in range(0, min(k, n) + 1):
        for subset in combinations(range(n), size):
            # Try to schedule this subset greedily by min-capital order.
            # The optimal order for a fixed subset is by capital ascending (intuitive),
            # but to be a true oracle, try all permutations.
            from itertools import permutations as _perm
            for order in _perm(subset):
                cw = w
                ok = True
                for idx in order:
                    if capital[idx] > cw:
                        ok = False
                        break
                    cw += profits[idx]
                if ok and cw > best:
                    best = cw
    return best


def edge_cases() -> None:
    # LC example.
    assert find_maximized_capital_two_heap(2, 0, [1, 2, 3], [0, 1, 1]) == 4
    assert find_maximized_capital_sort(2, 0, [1, 2, 3], [0, 1, 1]) == 4

    # k > n.
    assert find_maximized_capital_two_heap(10, 0, [1, 2], [0, 0]) == 3

    # Nothing affordable.
    assert find_maximized_capital_two_heap(2, 0, [10, 20], [5, 5]) == 0

    # k=0.
    assert find_maximized_capital_two_heap(0, 5, [1, 2, 3], [0, 0, 0]) == 5

    # Single project affordable.
    assert find_maximized_capital_two_heap(1, 1, [5, 10], [1, 100]) == 6


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(200):
        n = rng.randint(1, 5)
        k = rng.randint(0, 5)
        w = rng.randint(0, 5)
        profits = [rng.randint(0, 8) for _ in range(n)]
        capital = [rng.randint(0, 8) for _ in range(n)]

        two_heap = find_maximized_capital_two_heap(k, w, profits[:], capital[:])
        sort_v = find_maximized_capital_sort(k, w, profits[:], capital[:])
        brute = find_maximized_capital_brute(k, w, profits[:], capital[:])

        assert two_heap == sort_v == brute, (k, w, profits, capital, two_heap, sort_v, brute)


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")