class Solution:

    # M = len(difficulties), N = len(workers)
    # time = O(M log M + N log N + M + N), but can omit the M and N
    # space = O(M)
    def max_profit_assignment(self, difficulty, profits, workers):
        jobs = list(zip(difficulty, profits))
        jobs.sort() # will sort by the first tuple element
        index, best_so_far, result = 0, 0, 0
        
        for worker in sorted(workers):
            while index < len(jobs) and worker >= jobs[index][0]:
                best_so_far = max(best_so_far, jobs[index][1])
                index += 1
            
            result += best_so_far
        
        return result

difficulty = [2,4,6,8,10]
profits = [10,20,30,40,50]
workers = [4,5,6,7]

solution = Solution()
print(solution.max_profit_assignment(difficulty, profits, workers))