from heapq import heappush, heappop


def maximum_capital(c, k, capitals, profits):

    current_capital = c
    capitals_min_heap = []
    profits_max_heap = []

    # Insert all capitals values to a min-heap
    for x in range(0, len(capitals)):
        heappush(capitals_min_heap, (capitals[x], x))

    # Calculate capital of all the required number of projects
    # containing maximum profit
    for _ in range(k):

        # Select projects (in the range of the current capital)
        # then push them onto the max-heap

        # As, heapq is a min heap, but we need a max heap
        # so we will store negated elements
        while capitals_min_heap and capitals_min_heap[0][0] <= current_capital:
            c, i = heappop(capitals_min_heap)
            # push a negated element
            heappush(profits_max_heap, (-profits[i]))
        
        # check if the max-heap is empty
        if not profits_max_heap:
            break

        # Select those projects from the max-heap that contain the maximum profit
        # pop a negated element
        j = -heappop(profits_max_heap)
        print(f"\t\tUpdated capital = {current_capital} + {j}")
        current_capital = current_capital + j

    return current_capital


def main():
    input = (
              (0, 1, [1, 1, 2], [1 ,2, 3]),
              (1, 2, [1, 2, 2, 3], [2, 4, 6, 8]),
              (2, 3, [1, 3, 4, 5, 6], [1, 2, 3, 4, 5]),
              (1, 3, [1, 2, 3, 4], [1, 3, 5, 7]),
              (7, 2, [6, 7, 8, 10], [4, 8, 12, 14]),
              (2, 4, [2, 3, 5, 6, 8, 12], [1, 2, 5, 6, 8, 9])
            )
    num = 1
    for i in input:
        print(f"{num}.\tProject capital requirements:  {i[2]}")
        print(f"\tProject expected profits:      {i[3]}")
        print(f"\tNumber of projects:            {i[1]}")
        print(f"\tStart-up capital:              {i[0]}")
        print("\n\t\tProcessing: ")
        print("\n\tMaximum capital earned: ",
              maximum_capital(i[0], i[1], i[2], i[3]))
        print("-" * 100, "\n")
        num += 1


if __name__ == "__main__":
    main()