We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job. 
Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i]. 
Every worker can be assigned at most one job, but one job can be completed multiple times.
For example, if 3 people attempt the same job that pays $1, then the total profit will be $3.  If a worker cannot complete any job, his profit is $0.
What is the most profit we can make?
Example 1:
Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100 
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] seperately.
Notes:

1 <= difficulty.length = profit.length <= 10000
1 <= worker.length <= 10000
difficulty[i], profit[i], worker[i]  are in range [1, 10^5]

Difficulty: interview

Starter code:

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        

Solutions:
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        ws = sorted(worker, reverse=True)
        dp = sorted(zip(difficulty, profit), key=lambda x: x[1], reverse=True)
        # print(list(dp))
        
        i = 0
        total = 0
        for w in ws:
            while dp[i][0] > w:
                i = i + 1
                if i >= len(dp):
                    return total
            total = total + dp[i][1]
        return total

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        job = sorted(zip(difficulty, profit))

        best = 0 
        i = 0 
        profit = 0

        for work in sorted(worker):
            while (i < len(difficulty) and job[i][0] <= work):
                best = max(best, job[i][1])
                i += 1
            profit += best

        return profit

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        rel = zip(difficulty, profit)
        rel = sorted(rel)
        output = 0
        worker.sort()
        mx = 0
        j = 0
        for i in worker:
            while j < len(rel) and i >= rel[j][0]:
                mx = max(mx, rel[j][1])
                j += 1
            print(i, mx)
            output += mx
        return output

# 6:12 -> 6:25 | 7:23 -> 
# Find mapping of workers to jobs such that profit is maximized
# Greedy approach: take highest profit job, assign it to most highly skilled worker
from queue import PriorityQueue
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        # print('difficulty', difficulty)
        # print('profit', profit)
        # print('worker', worker)
        pq = PriorityQueue()
        
        worker.sort()
        
        for i, job in enumerate(profit):
            pq.put( (-job, i) )
        
        profit = 0
        
        while worker:
            skill = worker.pop()
            cash, diff_index = pq.get() if not pq.empty() else (0, -1)
            while not pq.empty() and diff_index > -1 and skill < difficulty[diff_index]:
                cash, diff_index = pq.get()
            if skill < difficulty[diff_index]:
                cash, diff_index = 0, -1
            if cash != 0:
                pq.put( (cash, diff_index) )
            cash *= -1
            profit += cash
            # print(profit, cash, skill)
        
        return profit

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = [[0,0]] + sorted([[difficulty[i], profit[i]] for i in range(len(profit))]) 
        for i in range(1, len(jobs)):
            jobs[i][1] = max(jobs[i-1][1], jobs[i][1])
        res, workerCounts = 0, collections.Counter(worker) 
        def binarySearch(n):
            l, r = 0, len(jobs)-1
            while l < r-1:
                
                mid = (l+r)//2
                if jobs[mid][0] > n:
                    r =  mid - 1
                else:
                    l = mid
            return jobs[l][1] if jobs[r][0] > n else jobs[r][1]
                
        for work, count in list(workerCounts.items()):
            res += binarySearch(work)*count
        return res



class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        
        temp = sorted( zip(difficulty, profit) )
        
        d = collections.defaultdict(int)
        
        for u, v in temp:
            d[u] = v
        
        maxdifficulty = max(worker)
        
        for i in range(1, maxdifficulty + 1):
            d[i] = max(d[i], d[i - 1])
            
        # print (d)
            
        ans = 0
        
        for i in worker:
            
            # print (i, d[i])
            
            ans += d[i]
            
        return ans
                
        
        
        
        
        
        


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        d = sorted([(difficulty[i],profit[i]) for i in range(len(difficulty))])
        c = [0] * 100005
        
        # print(d)
        
        t = 0
        for i in range(1,100005):
            c[i] = c[i-1]
            while t < len(d) and i == d[t][0]:
                c[i] = max(c[i],d[t][1])
                t += 1
                
        
        # print(c[0:101])
        # print([c[i] for i in worker])
        
        return sum([c[i] for i in worker])

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        max_v = max(max(difficulty), max(worker))
        
        n = len(difficulty)
        best = [0] * (max_v + 1)
        for i in range(n):
            d = difficulty[i]
            p = profit[i]
            best[d] = max(best[d], p)
        
        for i in range (1, max_v + 1):
            best[i] = max(best[i - 1], best[i])
        
        s = 0 
        for d in worker:
            s += best[d]
        return s

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        arr=[0 for _ in range(10**5+1)]
        for i in range(len(profit)):
            arr[difficulty[i]]=max(profit[i],arr[difficulty[i]])
        for i in range(1,10**5+1):
            arr[i]=max(arr[i-1],arr[i])
        ans=0
        # print(arr[:101])
        for i in worker:
            ans+=arr[i]
        return ans


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        output=0
        job=sorted(zip(difficulty,profit),reverse=True,key=lambda x:x[1])
        worker=sorted(worker,reverse=True)
        jobIndex=0
        for workerCab in worker:
            # print(workerCab)
            
            while jobIndex<len(job):
                # print(jobIndex)
                if job[jobIndex][0]<=workerCab:
                    # print('find')
                    break
                else:
                    jobIndex+=1
            
            if jobIndex<len(job):
                output=output+job[jobIndex][1]
            # print(output,job[jobIndex][1])
        # print(job)
        return output

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        for i in range(len(difficulty)):
            difficulty[i] = (difficulty[i], profit[i])
        difficulty.sort(key = lambda x:x[0]) # O(NlogN)
        i, L = 0, len(difficulty)
        ans, most = 0, 0
        for wker in sorted(worker):
            while i < L and difficulty[i][0] <= wker:
                most = max(most, difficulty[i][1])
                i += 1
            ans += most
        return ans

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = []
        total = 0
        
        for i in range(len(profit)):
            jobs.append([difficulty[i], profit[i]])
        print(jobs)
        
        worker.sort()
        jobs.sort()
        i = 0
        best = 0
        
        for work in worker:
            while i < len(jobs) and work >= jobs[i][0]:
                best = max(best, jobs[i][1])
                i += 1
            total += best
        
        return total
            


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = sorted(zip(difficulty, profit))
        worker.sort()

        m = len(worker)
        n = len(jobs)

        j = 0
        max_profit = 0
        result = 0
        for i in range(m):
            ability = worker[i]

            while j < n and jobs[j][0] <= ability:
                max_profit = max(max_profit, jobs[j][1])
                j += 1

            result += max_profit

        return result


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        best = 0
        tot = 0
        worker.sort()
        for d, p in sorted(zip(difficulty, profit)):
            while worker and d > worker[0]:
                tot += best
                worker.pop(0)
            best = max(best, p)
        tot += best * len(worker)
        return tot
        
            


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        l = sorted(zip(profit,difficulty), reverse = True)
        
        worker.sort(reverse = True)
        
        p = 0
        
        for w in worker:
            while l and w < l[0][1]:
                l.pop(0)
            if not l:
                break
            p+=l[0][0]
        return p

import bisect
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        m,n={},len(difficulty)
        for ind, val in enumerate(difficulty):
            m[val]=max(m.get(val,0),profit[ind])
        difficulty.sort()
        for ind, val in enumerate(difficulty):
            if ind>0:
                m[val]=max(m[val],m[difficulty[ind-1]])
        
        ans = 0
        for ind, val in enumerate(worker):
            d_ind = bisect.bisect_left(difficulty, val)
            if d_ind<n:
                if difficulty[d_ind]<=val:
                    ans+=m[difficulty[d_ind]]
                else:
                    ans+=m[difficulty[d_ind-1]] if d_ind>0 else 0
            else:
                ans+=m[difficulty[d_ind-1]]
        return ans


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        difficulty, profit = zip(*sorted(zip(difficulty, profit)))
        
        
        profit_table = {} # maps difficulty to profit
        
        for i, (d, p) in enumerate(zip(difficulty, profit)):
            if i > 0:
                profit_table[d] = max(p, profit_table[difficulty[i-1]])
            else:
                profit_table[d] = p
        
        value = 0
        
        d_index = len(difficulty) - 1
        for w in reversed(sorted(worker)):
            while d_index >= 0 and difficulty[d_index] > w:
                d_index -= 1
            if d_index >= 0: value += profit_table[difficulty[d_index]]
        return value

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = sorted(zip(difficulty, profit))
        profit = i = maxprofits = 0
        for ability in sorted(worker):
            while i < len(jobs) and ability >= jobs[i][0]:
                profit = max(jobs[i][1], profit)
                i += 1
            maxprofits += profit
        return maxprofits

import bisect
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        if not difficulty:
            return 0
        indices = sorted(list(range(len(difficulty))), key=lambda i: difficulty[i])        
        difficulty = [difficulty[i] for i in indices]
        profit = [profit[i] for i in indices]
        max_profit = [profit[0]]
        for p in profit[1:]:
            max_profit.append(max(max_profit[-1], p))
        total = 0            
        for ability in worker:
            idx = bisect.bisect_right(difficulty, ability)
            if idx > 0:
                total += max_profit[idx-1]
        return total                


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        if difficulty is None: return 0
        thislist = []
        for i in range(0, len(difficulty)): thislist.append((difficulty[i], profit[i]))
        thislist.sort()
        worker.sort()
        res = 0
        curr_max = 0
        worker_index = 0
        list_index = 0
        while worker_index < len(worker) and list_index < len(thislist):
            if thislist[list_index][0] <= worker[worker_index]:
                curr_max = max(curr_max, thislist[list_index][1])
                list_index += 1
            else:
                res += curr_max
                worker_index += 1
        
        if worker_index < len(worker): res += curr_max*(len(worker)-worker_index)
        return res

import bisect

class Solution:
    def solve(self, diff, profit, worker):
        mp = {}
        for i in range(len(diff)):
            d = diff[i]
            p = profit[i]
            if d not in mp:
                mp[d] = 0
            mp[d] = max(mp[d], p)
        diff2 = sorted(mp.keys())
        ln = len(diff2)
        mx = [0]*ln
        for i in range(ln):
            d = diff2[i]
            p = mp[d]
            if i == 0:
                mx[i] = p
            else:
                mx[i] = max(mx[i-1], p)
        total = 0
        # print(diff2)
        # print(profit2)
        # print(mx)
        # print('---')
        for w in worker:
            if w < diff2[0]:
                continue
            i = bisect.bisect_left(diff2, w)
            if i >= len(diff2):
                i = len(diff2)-1                
            elif diff2[i] > w:
                i -= 1
                if i < 0:
                    continue
            max_profit = mx[i]
            # print(w, i, mx[i])
            total += max_profit
        return total
    
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        return self.solve(difficulty, profit, worker)


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        combined = sorted(zip(difficulty,profit))
        worker.sort()
        n = len(worker)
        start = 0
        net_profit = 0
        current_profit = 0
        for i in range(n):
            while start< len(difficulty) and combined[start][0]<=worker[i]:
                current_profit = max(combined[start][1],current_profit)
                start += 1
            net_profit += current_profit
        return net_profit

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        value = list(zip(difficulty, profit))
        value.sort()
        print(value)
        res = 0
        i = 0
        best = 0
        for person in sorted(worker):
            while i < len(value) and person >= value[i][0]:
                best = max(best, value[i][1])
                i += 1
            res += best
        
        return res

class Solution:
    def maxProfitAssignment(
        self, difficulty: List[int], profit: List[int], worker: List[int]
    ) -> int:

        pairs = [(a, b) for a, b in zip(difficulty, profit)]
        sorted_pairs = sorted(pairs, key=lambda p: p[0])
        benifit = []
        current_max = 0
        for diff, pro in sorted_pairs:
            current_max = max(pro, current_max)
            benifit.append((diff, current_max))

        sorted_workers = sorted(worker)
        ans = 0
        current_difficulty_index = worker_index = 0
        while worker_index < len(worker):
            if sorted_workers[worker_index] < benifit[current_difficulty_index][0]:
                worker_index += 1
                continue
            while (
                current_difficulty_index + 1 < len(worker)
                and benifit[current_difficulty_index + 1][0]
                <= sorted_workers[worker_index]
            ):
                current_difficulty_index += 1

            # print(
            #     f\"{worker_index=} {current_difficulty_index=} {benifit[worker_index][1]=}\"
            # )
            ans += benifit[current_difficulty_index][1]
            worker_index += 1

        return ans


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        worker.sort()
        arr=[]
        for i in range(len(profit)):
            arr.append([difficulty[i],profit[i]])
            
        arr.sort(key=lambda x:x[0])
        for i in range(len(arr)):
            difficulty[i] = arr[i][0]
            profit[i] = arr[i][1]
        # print(difficulty)
        # print(profit)
        # print(worker)
        prev = [profit[0]]
        for i in range(1,len(profit)):
            prev.append(max(profit[i],prev[-1]))
        i = 0
        p=0
        j = 0
        while(j<len(worker)):
            if(i==len(difficulty)):
                p+=prev[i-1]
                j+=1
                continue
                
            if(difficulty[i]<=worker[j]):
                i+=1
            # elif(difficulty[i]==worker[j]):
            #     # p+=prev[i]
            #     i+=1
            #     # j+=1
            else:
                x=i-1
                while(x>=0 and difficulty[x]>worker[j]):
                    x-=1
                if(x>=0):
                    p+=prev[x]
                j+=1
                
        return p


from bisect import bisect
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        
        maxp = 0
        maxpa = []
        for difficulty,profit in sorted(zip(difficulty,profit),key=lambda x:x[0]):
            maxp = max(maxp,profit)
            maxpa.append((difficulty,maxp))
            
        
        total = 0
        for w in worker:
            ind = bisect(maxpa,(w,float('inf')))
            if ind>0:
                total += maxpa[ind-1][1]
            
        return total

            
        
        


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        
        job = {}
        for cost, gain in zip(difficulty, profit):           
            if cost in job:
                job[cost] = max(job[cost], gain)
            else:
                job[cost] = gain
        
        job = [(k, v) for k, v in list(job.items())] + [(0, 0)]
        job.sort()
        useless = set()
        
        global_max = -float('inf')
        for i, (c, g) in enumerate(job):
            if g < global_max:
                useless.add(i)
            else:
                global_max = g
        
        job = [job[i] for i in range(len(job)) if i not in useless]
        print(job)
        worker.sort()
        
        i, j = 0, 0
        ans = 0
        while j < len(worker):
            
            while job[i][0] < worker[j] and i < len(job) - 1:
                i += 1
            
            ans += job[i][1] if job[i][0] <= worker[j] else job[i- 1][1]
            
            j += 1
        
        return ans


class Solution:
    def maxProfitAssignment(self, difficulty, profit, worker):
        
        data = sorted([(d,p) for d,p in zip(difficulty, profit)])
        worker.sort()
        i, n, money = 0, len(data), 0
        res = 0
        for w in worker:
            while i < n and w >= data[i][0]:
                money = max(money, data[i][1])
                i += 1
            res += money
        return res
        
        
        


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        mDifficulty = {}
        
        for i in range(len(difficulty)):
            d = difficulty[i]
            if difficulty[i] not in mDifficulty:
                mDifficulty[d] = 0
            mDifficulty[d] = max(mDifficulty[d], profit[i])
        
        jobs = []
        for key, value in mDifficulty.items():
            jobs.append([key, value]) 
            
        jobs.sort(key=lambda job:job[0])
        
        for i in range(1, len(jobs)):
            jobs[i][1] = max(jobs[i][1], jobs[i - 1][1])
            
        worker.sort()
        start = len(jobs) - 1
        count = 0
        
        for i in range(len(worker) - 1, - 1, -1):
            while worker[i] < jobs[start][0] and start >= 0:
                start -= 1
            if start < 0:
                break
            count += jobs[start][1]
            
        return count

class Solution(object):
    def maxProfitAssignment(self, difficulty, profit, worker):
        jobs = zip(difficulty, profit)
        jobs = sorted(jobs)
        ans = i = best = 0
        for skill in sorted(worker):
            while i < len(jobs) and skill >= jobs[i][0]:
                best = max(best, jobs[i][1])
                i += 1
            ans += best
        return ans

class Solution:
    def maxProfitAssignment(self, difficulty, profit, worker):
        jobs = sorted(zip(difficulty, profit))
        ans = i = best = 0
        for skill in sorted(worker):
            while i < len(jobs) and skill >= jobs[i][0]:
                best = max(best, jobs[i][1])
                i += 1
            ans += best
        return ans

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        arr = []
        for i in range(len(difficulty)):
            arr.append((difficulty[i], profit[i]))
        arr = sorted(arr, key=lambda x: x[0])

        maxProfit, maxProfits = 0, []
        for _, gain in arr:
            maxProfit = max(maxProfit, gain)
            maxProfits.append(maxProfit)

        total = 0
        for person in worker:
            idx = self.uppperBsearch(arr, person) - 1
            if idx > -1:
                total += maxProfits[idx]

        return total

    def uppperBsearch(self, arr, target):
        left = 0
        right = len(arr)
        while left < right:
            mid = (left + right)//2
            if target >= arr[mid][0]:
                left = mid + 1
            else:
                right = mid
        return right

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        ls = sorted(range(len(difficulty)), key= lambda x : difficulty[x])
        workers = sorted(worker)
        
        idx = 0
        resp = 0
        best = 0
        for worker in workers:
            while idx < len(ls) and worker >= difficulty[ls[idx]]:
                best = max(best, profit[ls[idx]])
                idx += 1
            resp += best
        return resp

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = sorted(zip(difficulty, profit),key=lambda t:t[0])
        ans = i = best = 0
        for w in sorted(worker):
            while i < len(jobs) and w >= jobs[i][0]:
                best = max(best, jobs[i][1])
                i += 1
            ans += best
        return ans

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        tup=[]
        dic = {}
        for i in range(0,len(profit)):
            tup.append((profit[i],difficulty[i]))
      
        worker.sort(reverse=True)        
        tup.sort(reverse=True)
        indx=0
        t_indx=0
        
        res=0
        
        while(indx<len(worker)):
            
            while(t_indx < len(profit) and worker[indx]<tup[t_indx][1]):
                t_indx+=1             
                
            if(t_indx < len(profit)):
                res+=tup[t_indx][0]
            indx+=1
        
        return res
            
            
            
            
        
        


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        worker = sorted(worker)
        jobs = sorted([(-1,0)]+[(difficulty[i],profit[i])for i in range(len(difficulty))])
        job_nums = len(jobs)
        maxProfit = 0
        job_index = 0
        res = 0
        for ability in worker:
            while job_index < job_nums-1 and ability>= jobs[job_index+1][0]:
                job_index+=1
                maxProfit = max(maxProfit,jobs[job_index][1])
            res+=maxProfit
        return res
            
        
        


class Solution(object):
    def maxProfitAssignment(self, difficulty, profit, worker):
        arr = []
        for d, p in sorted(zip(difficulty, profit)):
            if arr and arr[-1][1]>=p:
                continue
            arr.append([d, p])    
        
        N = len(arr)
        res, i, best = 0, 0, 0
        for w in sorted(worker):
            while i<N and w>=arr[i][0]:
                best = arr[i][1]
                i += 1
            
            res += best
        return res


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        tup_list = sorted(list(zip(difficulty, profit)))
        filtered_list = []
        best = 0
        for d, p in tup_list:
            if p > best:
                best = p
                filtered_list.append((d, p))

        worker = sorted(worker)

        profit = 0

        dix = 0
        for w in worker:
            if w < filtered_list[dix][0]:
                continue

            while dix+1 < len(filtered_list) and filtered_list[dix+1][0] <= w:
                dix += 1

            profit += filtered_list[dix][1]

        return profit

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        
        val_dict = dict()
        for i in range(len(difficulty)):
            val_dict[difficulty[i]] = max(val_dict.get(difficulty[i], 0), profit[i])
        key_list = list(val_dict.keys())
        key_list = sorted(key_list)

        max_val = 0
        max_list = [0] * len(key_list)
        for i in range(len(key_list)):
            max_val = max(max_val, val_dict[key_list[i]])
            max_list[i] = max_val
        
        total = 0
        #print(key_list, max_list)
        for w in worker:
            #print(w, self.bisect(w, key_list, max_list))
            total += self.bisect(w, key_list, max_list)
        return total
    
    def bisect(self, w, key_list, max_list):

        left, right = 0, len(key_list)-1
        if w < key_list[0]:
            return 0
        if w >= key_list[right]:
            return max_list[right]

        while left != right - 1:
            mid = (left + right) // 2
            if w > key_list[mid]:
                left = mid
            elif w < key_list[mid]:
                right = mid
            else:
                return max_list[mid]
        return max_list[left]

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        # 8:49 9/26/20
        
        def find_difficulty(d, w):
            n = len(d)
            lt, rt = 0, n
            while lt < rt:
                mid = lt + (rt - lt) // 2
                if d[mid] == w:
                    return mid
                elif d[mid] > w:
                    rt = mid
                else:
                    lt = mid + 1
            return rt-1

        difficulty1 = sorted(difficulty)
        
        difficulty = list(zip(difficulty, profit))
        difficulty.sort(key = lambda x: (x[0]))
        
        profit = {}
        max_profit = 0
        for i in range(len(difficulty)):
            if difficulty[i][0] not in profit or profit[difficulty[i][0]] < difficulty[i][1]:
                profit[difficulty[i][0]] = difficulty[i][1]
            max_profit = max(max_profit, profit[difficulty[i][0]])
            profit[difficulty[i][0]] = max_profit
                
        
        total = 0
        pre = -1
        for i in range(len(worker)):
            # if i > 0 and worker[i] == worker[i-1] and pre != -1:
            #     total += profit[pre]
            #     continue
            pre = find_difficulty(difficulty1, worker[i])
            if pre != -1:
                total += profit[difficulty1[pre]]
                
        return total
            
        


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = list(zip(difficulty, profit))
        jobs.sort(key=lambda x:x[1], reverse=True)
        jobs.sort(key=lambda x:x[0])
        bestjobs=[]
        res = 0
        for a,b in jobs:
            if not bestjobs:
                bestjobs.append((a,b))
            elif bestjobs[-1][1]<b:
                bestjobs.append((a,b))
        print(bestjobs)
        for wo in worker:
            lo, hi = 0, len(bestjobs)-1
            while lo<hi:
                mid = (lo+hi+1)//2
                if bestjobs[mid][0]>wo:
                    hi = mid-1
                else:
                    lo = mid
            if bestjobs[lo][0]<=wo:
                res+=bestjobs[lo][1]
        return res


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        m = len(difficulty)
        
        difficulty, profit = zip(*sorted(zip(difficulty, profit)))
        
        difficulty = list(difficulty)
        profit = list(profit)
        
        best_profit = m * [0]
        best_profit[0] = profit[0]
        ind = 0
        prev_v = difficulty[0]
        
        for i in range(1, m):
            if prev_v != difficulty[i]:
                ind += 1
                difficulty[ind] = prev_v = difficulty[i]
                best_profit[ind] = best_profit[ind - 1]
            
            best_profit[ind] = max(best_profit[ind], profit[i])
            
        # print(best_profit)
        # print(difficulty)
            
        m = ind + 1
            
        def bins(target):
            start = 0
            end = m - 1
            bsres = 0
            
            while start <= end:
                middle = start + (end - start) // 2
                
                if difficulty[middle] == target:
                    return best_profit[middle]
                
                if difficulty[middle] < target:
                    bsres = best_profit[middle]
                    start = middle + 1
                    
                else:
                    end = middle - 1
                    
            return bsres
        
        res = 0
        h = dict()
        
        for w in worker:
            if w not in h:
                h[w] = bins(w)
            
            res += h[w]
        
        return res

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        m = len(difficulty)
        
        difficulty, profit = zip(*sorted(zip(difficulty, profit)))
        
        difficulty = list(difficulty)
        profit = list(profit)
        
        best_profit = m * [0]
        best_profit[0] = profit[0]
        ind = 0
        prev_v = difficulty[0]
        
        for i in range(1, m):
            if prev_v != difficulty[i]:
                ind += 1
                difficulty[ind] = prev_v = difficulty[i]
                best_profit[ind] = best_profit[ind - 1]
            
            best_profit[ind] = max(best_profit[ind], profit[i])
            
        # print(best_profit)
        # print(difficulty)
            
        m = ind + 1
            
        def bins(target):
            start = 0
            end = m - 1
            bsres = 0
            
            while start <= end:
                middle = start + (end - start) // 2
                
                if difficulty[middle] == target:
                    return best_profit[middle]
                
                if difficulty[middle] < target:
                    bsres = best_profit[middle]
                    start = middle + 1
                    
                else:
                    end = middle - 1
                    
            return bsres
        
        res = 0
        h = dict()
        
        for w in worker:
            # if w not in h:
                # h[w] = bins(w)
            
            res += bins(w)
        
        return res

# 20201007 1:23 am ref
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = sorted(zip(difficulty, profit))
        profit = i = maxprofits = 0
        for ability in sorted(worker):
            while i < len(jobs) and ability >= jobs[i][0]:
                profit = max(jobs[i][1], profit)
                i += 1
            maxprofits += profit
        return maxprofits

from heapq import *

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        worker.sort()
        difficulty_min_heap = []
        profit_max_heap = []
        
        total = 0
        
        for i in range(len(profit)):
            heappush(difficulty_min_heap, (difficulty[i], i))
            
            
        for w in worker:
            while difficulty_min_heap and difficulty_min_heap[0][0] <= w:
                current_difficulty, job_id = heappop(difficulty_min_heap)
                heappush(profit_max_heap, (-profit[job_id], job_id))
            if profit_max_heap:
                total += -profit_max_heap[0][0]
            
        return total
                
                
            
        
        


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        def binary_search(arr, target):
            l, r = 0, len(arr) - 1
            res = -1
            while l <= r:
                mid = (l + r) // 2
                if arr[mid][0] <= target:
                    res = mid
                    l = mid + 1
                else:
                    r = mid - 1
            return res        
        jobs = sorted([d, p] for d,p in zip(difficulty, profit))    
        for i in range(1,len(jobs)):
            jobs[i][1] = max(jobs[i][1], jobs[i - 1][1])    
        res = 0
        for w in worker:
            i = binary_search(jobs, w)
            if i == -1:
                continue
            res += jobs[i][1]    
        return res    

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        for i in range(len(profit)):
            difficulty[i] = [difficulty[i], profit[i]]
        difficulty.sort()
        for i in range(1, len(profit)):
            difficulty[i][1] = max(difficulty[i-1][1], difficulty[i][1])
        
        def search(d):
            if d < difficulty[0][0]:
                return -1
            l = 0
            r = len(profit)-1
            
            while l < r:
                m = (l+r+1)//2
                if difficulty[m][0] <= d:
                    l = m
                else:
                    r = m-1
            return l
        
        res = 0
        for w in worker:
            i = search(w)
            if i >= 0:
                res += difficulty[i][1]
        return res


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = [[difficulty[i],profit[i]] for i in range(len(difficulty))]
        jobs.sort()
        
        worker.sort()
        
        ans, best ,i = 0, 0,0
        
        
        for skill in worker:
            while i < (len(jobs)) and skill >= jobs[i][0]:
                best = max(best,jobs[i][1])
                i += 1
            ans += best
        return ans

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        n = len(worker)
        jobs =  sorted(zip(difficulty, profit))
        total = 0
        best = 0
        i = 0
        for ability in sorted(worker):
            while i < len(jobs) and ability >= jobs[i][0]:
                best = max(jobs[i][1], best)
                i += 1
            total += best
        return total


class Solution:
    def maxProfitAssignment(self, d: List[int], p: List[int], work: List[int]) -> int:
        N, maxd = len(p), max(d)
        cmb = [(d[i], p[i]) for i in range(N)]
        cmb.sort()
        
        dd = [0]*(maxd+1)
        val = j = 0
        for i in range(maxd+1):
            while j<N and i >= cmb[j][0]:
                val = max(val, cmb[j][1])
                j += 1
            dd[i] = val 
         
        # print(dd)
        ans = 0
        for w in work:
            if w>maxd:
                ans += dd[maxd]
            else:
                ans += dd[w]
        
        return ans

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        _max=max(worker)+1
        make=[0]*_max
        num=[(difficulty[i],profit[i])for i in range(len(profit)) if difficulty[i]<_max]
        num.sort(key=lambda x:x[0])
        p_max=0
        for i in range(len(num)):
            if num[i][1]>=p_max:
                make[num[i][0]]=num[i][1]
                p_max=num[i][1]
        pre=-1
        for i in range(len(make)):
            if make[i]!=0:
                pre=make[i]
            elif pre!=-1:
                make[i]=pre
        ans=0
        for w in worker:
            ans+=make[w]
        return ans 

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        dp = {}
        for i, d in enumerate(difficulty):
            dp[d] = max(profit[i], dp.get(d, 0))
        dp = sorted([ (d,p) for d, p in dp.items() ])

        d2p = []
        pre = 0
        for d, p in dp:
            pre = max(pre, p)
            d2p.append((d, pre))

        def getjob(work, pv, pw, pi):
            l, r = 0, len(d2p) - 1
            if d2p[l][0] > work: return 0, 0 
            if d2p[r][0] <= work: return d2p[r][1], r
            l = pi

            while l <= r:
                i = (l + r) // 2
                if d2p[i][0] == work:
                    return max(d2p[i][1], pv), i
                if d2p[i][0] > work:
                    r = i - 1
                else:
                    l = i + 1
            if i == r:
                return max(d2p[i][1], pv), i
            return max(d2p[i-1][1], pv), i - 1

        rs = 0
        pv = 0
        pw = 0
        pi = 0
        for w in sorted(worker):
            pv, pi = getjob(w, pv, pw, pi)
            pw = w
            rs += pv
        return rs

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        dp = {}
        for i, d in enumerate(difficulty):
            dp[d] = max(profit[i], dp.get(d, 0))
        dp = sorted([ (d,p) for d, p in dp.items() ])

        d2p = []
        pre = 0
        for d, p in dp:
            pre = max(pre, p)
            d2p.append((d, pre))

        def getjob(work):
            l, r = 0, len(d2p) - 1
            if d2p[l][0] > work: return 0
            if d2p[r][0] <= work: return d2p[r][1]

            while l <= r:
                i = (l + r) // 2
                if d2p[i][0] == work:
                    return d2p[i][1]
                if d2p[i][0] > work:
                    r = i - 1
                else:
                    l = i + 1
            if i == r:
                return d2p[i][1]
            return d2p[i-1][1]

        rs = 0
        for w in worker:
            rs += getjob(w)
        return rs

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        _max=max(worker)+1
        make=[0]*_max
        num=[(difficulty[i],profit[i])for i in range(len(profit)) if difficulty[i]<_max]
        num.sort(key=lambda x:x[0])
##        x=0
##        while x<len(num):
##            if x+1<len(num):
##                if num[x][1]>num[x+1][1]:
##                    num.pop(x+1)
##                else:x+=1
##            else:break
        p_max=0
        for i in range(len(num)):
            p_max=max(p_max,num[i][1])
            if num[i][1]>=p_max:make[num[i][0]]=num[i][1]
        pre=-1
##        print(make)
        for i in range(len(make)):
            if make[i]!=0:
                pre=make[i]
            elif pre!=-1:
                make[i]=pre
        ans=0
        for w in worker:
            ans+=make[w]
        return ans 

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = sorted([(difficulty[i], profit[i]) for i in range(len(difficulty))], key=lambda x: x[0])
        worker = sorted(worker)
        jobPointer = 0
        workerPointer = 0
        maxProfit = 0
        totalProfit = 0
        while True:
            if workerPointer >= len(worker):
                break
            talent = worker[workerPointer]
            if jobPointer >= len(jobs) or jobs[jobPointer][0] > talent:
                totalProfit += maxProfit
                workerPointer += 1
            else:
                if jobs[jobPointer][1] > maxProfit:
                    maxProfit = jobs[jobPointer][1]
                jobPointer += 1
        return totalProfit
        


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        
        _max=max(worker)+1
        make=[0]*_max
        num=[(difficulty[i],profit[i])for i in range(len(profit)) if difficulty[i]<_max]
        num.sort(key=lambda x:x[0])
        x=0
        while x<len(num):
            if x+1<len(num):
                if num[x][1]>num[x+1][1]:
                    num.pop(x+1)
                else:x+=1
            else:break
        for i in range(len(num)):
            make[num[i][0]]=num[i][1]
        pre=-1
        for i in range(len(make)):
            if make[i]!=0:
                pre=make[i]
            elif pre!=-1:
                make[i]=pre
        ans=0
        for w in worker:
            ans+=make[w]
        return ans       


class Solution:
    def maxProfitAssignment(self, d: List[int], p: List[int], work: List[int]) -> int:
        maxd = max(d)
        cmb1 = defaultdict(int)
        for i in range(len(p)):
            cmb1[d[i]] = max(cmb1[d[i]], p[i])
        
        cmb = sorted(cmb1.items(), key=lambda x: x[0])

        NN = len(cmb)
        dd = [0]*(maxd+1)
        val = j = 0
        for i in range(maxd+1):
            if j<NN and i == cmb[j][0]:
                val = max(val, cmb[j][1])
                j += 1
            dd[i] = val 
         
        
        ans = 0
        for w in work:
            if w>maxd:
                ans += dd[maxd]
            else:
                ans += dd[w]
        
        return ans

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = sorted(zip(difficulty, profit), key = lambda x: x[0])
        ans = i = best = 0
        for skill in sorted(worker):
            while i < len(jobs) and skill >= jobs[i][0]:
                best = max(best, jobs[i][1])
                i += 1
            ans += best
        return ans

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        
        
        def findProfit(ppl, goodJobs):
            l=0
            r=len(goodJobs)-1
            while l<r-1:
                test=int((l+r)/2)
                if goodJobs[test][1]>ppl:
                    l=test
                else:
                    r=test
            if goodJobs[r][1]>ppl:
                return 0
            elif goodJobs[l][1]>ppl:
                return goodJobs[r][0]
            return goodJobs[l][0]
                
        
        goodJobs=[]
        jobs=[(profit[i], difficulty[i]) for i in range(len(difficulty))]
        jobs=sorted(jobs, key=lambda job:job[0], reverse=True)
        goodJobs.append(jobs[0])
        for i in range(1,len(jobs)):
            if jobs[i][1]<goodJobs[-1][1]:
                goodJobs.append(jobs[i])
        ans=0
        print((goodJobs, worker))
        for ppl in worker:
            ans=ans+findProfit(ppl, goodJobs)
            print(ans)
        return ans
         


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = list(zip(difficulty, profit))
        jobs = sorted(jobs, key=lambda x: x[0])
        worker.sort()
        idx = 0
        ans = 0
        p = 0
        for skill in worker:
            while idx < len(jobs) and jobs[idx][0] <= skill:
                p = max(p, jobs[idx][1])
                idx += 1
            ans += p
        return ans
        
    
    


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        worker.sort()
        difprof = [(difficulty[i], profit[i]) for i in range(len(difficulty))]
        difprof.sort()
        total = 0
        
        index = 0
        maxProfit = 0
        for w in worker:
            while index < len(difprof) and w >= difprof[index][0]:
                maxProfit = max(maxProfit, difprof[index][1])
                index += 1
            
            total += maxProfit
        return total
            
#         n = len(worker)
#         dp = [0 for i in range(worker[n - 1]+1)]
        
#         index = 0
#         for i in range(1, len(dp)):
#             if index < len(difficulty) and i == difficulty[index]:
#                 dp[i] = max(dp[i-1], profit[index])
#                 index += 1
#             else:
#                 dp[i] = dp[i-1]
        
#         total = 0
#         for w in worker:
#             total += dp[w]
            
#         return total


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        profit = [i[1] for i in sorted(zip(difficulty, profit))]
        difficulty.sort()
        for i in range(1, len(profit)):
            profit[i] = max(profit[i], profit[i-1])
        difficulty.append(float('inf'))
        tot = 0
        for w in range(len(worker)):
            low = 0
            high = len(difficulty)-1
            while low < high:
                mid = low + (high-low)//2
                if difficulty[mid] > worker[w]:
                    high = mid
                else:
                    low = mid+1
            low -= 1
            if low < 0:
                continue
            tot += profit[low]
        return tot


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = sorted(zip(difficulty, profit))
        res = i = best = 0
        for ability in sorted(worker):
            while i < len(jobs) and ability >= jobs[i][0]:
                best = max(jobs[i][1], best)
                i += 1
            res += best
        return res

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        mapProfit = dict()
        for i in range(len(difficulty)):
            if difficulty[i] in mapProfit:
                mapProfit[difficulty[i]] = max(mapProfit[difficulty[i]], profit[i])
            else:
                mapProfit[difficulty[i]] = profit[i]
        l = list()
        maxDiff = max(difficulty)
        for i in range(maxDiff + 1):
            if i in mapProfit:
                l.append(mapProfit[i])
            else:
                l.append(0)
        
        maxFromBegin = 0
        for i in range(len(l)):
            if l[i] < maxFromBegin:
                l[i] = maxFromBegin
            else:
                maxFromBegin = l[i]
        # print(l)
        res = 0
        for work in worker:
            if work > maxDiff:
                res += l[-1]
            else:
                res += l[work]
        return res

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        n=len(profit)
        maxm=max(difficulty)
        dp=[0]*(1+maxm)
        for i in range(n):
            dp[difficulty[i]]=max(dp[difficulty[i]],profit[i])
        for i in range(1,maxm+1):
            dp[i]=max(dp[i],dp[i-1])
        res=0

        for x in worker:
            if x>maxm:
                res+=dp[maxm]
            else:
                res+=dp[x]
        return res


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        # Max profits for each level of difficulty.
        max_diff = max(difficulty)
        max_profits = [0] * (max_diff + 1)
        
        # Set the initial values
        for diff, profit in zip(difficulty, profit):
            max_profits[diff] = max(max_profits[diff], profit)
        
        # Consider the profit from lower difficulty (ie. diff 1 profit 5 might be better than diff 5 profit 1)
        for i in range(1, max_diff + 1):
            max_profits[i] = max(max_profits[i], max_profits[i - 1])
        
        # Figure out max profits.
        pft = 0
        for wskill in worker:
            pft += max_profits[max_diff if wskill > max_diff else wskill]
        
        return pft
        


from bisect import bisect_right

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        dp = [(d, p) for d, p in zip(difficulty, profit)]
        dp.sort()
        G = []
        C = []
        for x, y in dp:
            if not G or G[-1] < x:
                G.append(x)
                C.append(y)
                continue
            if G[-1] == x:
                C[-1] = y
        for y in range(1, len(C)):
            if C[y-1] > C[y]:
                C[y] = C[y-1]
        ans = 0
        for w in worker:
            idx = bisect_right(G, w)-1
            if idx >= 0:
                ans += C[idx]
        return ans

def maximum_profit_for_difficulty(diff_job, difficulty, profit):
    return max([profit[job] for job in diff_job[difficulty]])

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        min_difficulty = min(difficulty)
        max_difficulty = max(difficulty)
        least_difficult_job = difficulty.index(min_difficulty)
        
        diff_job = defaultdict(list)
        for i, diff in enumerate(difficulty):
            diff_job[diff].append(i)
    
        max_profit = [maximum_profit_for_difficulty(diff_job, min_difficulty, profit)]
        for i in range(1, max_difficulty-min_difficulty+1):
            current_difficulty = i + min_difficulty
            if current_difficulty in diff_job:
                current_job_profit = maximum_profit_for_difficulty(diff_job, current_difficulty, profit)
                max_profit.append(max(max_profit[i-1], current_job_profit))
            else:
                max_profit.append(max_profit[i-1])

        result = 0  
        for ability in worker:
            if ability >= max_difficulty:
                result += max_profit[-1]
            elif ability < min_difficulty:
                result += 0
            else:
                result += max_profit[ability-min_difficulty]
        return result


# # Fisrt solution
# def createListOfProfitDiff(profit, difficulty):
#     profit_diff = []
#     for i in range(len(profit)):
#         profit_diff.append((profit[i], difficulty[i]))
#     return profit_diff
        
        
        
# class Solution:
#     def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
#         profit_diff = createListOfProfitDiff(profit, difficulty)
#         profit_diff.sort(key=lambda x:x[0])
#         worker2 = sorted(worker)

#         maxprofit = 0
#         for i in range(len(profit_diff)-1, -1, -1):
#             for j in range(len(worker2) -1, -1, -1):
#                 if profit_diff[i][1]> worker2[j]:
#                     break
#                 else:
#                     maxprofit += profit_diff[i][0]
#                     worker2.pop(j)
#         return maxprofit
# Second solution
def createListOfProfitDiff(profit, difficulty):
    profit_diff = []
    for i in range(len(profit)):
        profit_diff.append((profit[i], difficulty[i]))
    return profit_diff
        
        
        
# class Solution:
#     def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
#         profit_diff = createListOfProfitDiff(profit, difficulty)
#         profit_diff.sort(key=lambda x:x[0])
#         worker2 = sorted(worker)

#         maxprofit = 0
#         i = len(profit_diff) -1
#         j = len(worker2)-1
#         while i<len(profit_diff) and j <len(worker2) and i>-1 and j>-1:
#             if profit_diff[i][1]> worker2[j]:
#                 i-=1
#             else:
#                 maxprofit += profit_diff[i][0]
#                 worker2.pop(j)
#                 j-=1
#         return maxprofit

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        w = sorted(worker)
        w.reverse()
        dp = []
        for i in range(len(profit)):
            dp.append((profit[i], difficulty[i]))
        dp.sort(key =  lambda x:x[0])
        dp.reverse()

        i = 0
        count = 0
        for p in dp:
            while i<len(w) and p[1] <= w[i]:
                count += p[0]
                i+=1
        return count
                


from itertools import chain
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        li = list(chain(zip(profit, difficulty)))
        li.sort()
        cutoffs = [li[-1][1]]
        profits = [li[-1][0]]
        for i in range(len(profit)-2, -1, -1):
            if li[i][1] < cutoffs[0]:
                cutoffs.insert(0, li[i][1])
                profits.insert(0, li[i][0])
        cutoffs.insert(0, 0)
        profits.insert(0, 0)
        ans = 0
        n = len(cutoffs)
        for ability in worker:
            l = 0
            r = n-1
            while(r >= l):
                mid = (l + r) // 2
                if ability == cutoffs[mid]:
                    break
                elif ability > cutoffs[mid]:
                    l = mid + 1
                else:
                    r = mid - 1
            mid = mid - 1
            for i in range(3):
                if mid+1 < n:
                    if ability >= cutoffs[mid+1]:
                        mid += 1
            ans += profits[mid]
        return(ans)

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        combined = []

        for i in range(len(difficulty)):
            combined.append((difficulty[i], profit[i]))

        combined = sorted(combined, key=lambda x: x[0])
        total = 0
        i = 0
        best_profit = 0
        
        for w in sorted(worker):
            while i < len(combined) and w >= combined[i][0]:
                best_profit = max(best_profit, combined[i][1])
                i += 1
            
            # best_profit is the most profit you can get for current worker, if the next worker has the same workload capability, he will do add to the total doing with the same best_profit.
            total += best_profit
            
        return total


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        profit = [i[1] for i in sorted(zip(difficulty, profit))]
        difficulty.sort()
        for i in range(1, len(profit)):
            profit[i] = max(profit[i], profit[i-1])
        difficulty.append(float('inf'))
        worker.sort()
        tot = 0
        low = 0
        for w in range(len(worker)):
            low = 0
            high = len(difficulty)-1
            while low < high:
                mid = low + (high-low)//2
                if difficulty[mid] > worker[w]:
                    high = mid
                else:
                    low = mid+1
            low -= 1
            if low < 0:
                low = 0
                continue
            tot += profit[low]
        return tot


def maximum_profit_for_difficulty(diff_job, difficulty, profit):
    return max([profit[job] for job in diff_job[difficulty]])

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        min_difficulty = min(difficulty)
        max_difficulty = max(difficulty)        
        diff_job = defaultdict(list)
        for i, diff in enumerate(difficulty):
            diff_job[diff].append(i)
    
        max_profit = [maximum_profit_for_difficulty(diff_job, min_difficulty, profit)]
        for i in range(1, max_difficulty-min_difficulty+1):
            current_difficulty = i + min_difficulty
            if current_difficulty in diff_job:
                current_job_profit = maximum_profit_for_difficulty(diff_job, current_difficulty, profit)
                max_profit.append(max(max_profit[i-1], current_job_profit))
            else:
                max_profit.append(max_profit[i-1])

        result = 0  
        for ability in worker:
            if ability >= max_difficulty:
                result += max_profit[-1]
            elif ability < min_difficulty:
                result += 0
            else:
                result += max_profit[ability-min_difficulty]
        return result


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = list(zip(difficulty, profit))
        jobs.sort()
        ans = 0
        i = 0
        best = 0
        for skill in sorted(worker):
            while i<len(jobs) and skill >= jobs[i][0]:
                best = max(best, jobs[i][1])
                i += 1
            
            ans += best
        
        return ans

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        
        n=max(worker)
        s=[0 for i in range(n)]
        
        for i in range(len(difficulty)):
            if difficulty[i]<=n :
                s[difficulty[i]-1]=max(s[difficulty[i]-1],profit[i])
        
        
        for i in range(1,n):
            if s[i]<s[i-1]:
                s[i]=s[i-1]
        ans=sum([s[worker[i]-1] for i in range(len(worker))])
        return ans

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        def bs(arr, s, e, target):
            while s<=e:
                mid = s+(e-s)//2
                if arr[mid][0]<=target:
                    s = mid+1
                else:
                    e = mid-1
            return e
        
        arr = []
        for pd in sorted(zip(difficulty, profit)):
            if arr and arr[-1][1]>=pd[1]:
                continue
            arr.append(pd)
            
        res = 0
        N = len(arr)
        for w in worker:
            idx = bs(arr, 0, N-1, w)
            if idx>=0:
                res += arr[idx][1]
            
        return res

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        n=len(profit)
        maxm=max(difficulty)
        dp=[0]*(1+maxm)
        for i in range(n):
            dp[difficulty[i]]=max(dp[difficulty[i]],profit[i])
        for i in range(1,maxm+1):
            dp[i]=max(dp[i],dp[i-1])
        res=0

        for x in worker:
            if x>maxm:
                res+=dp[maxm]
            else:
                res+=dp[x]
        return res

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        bfb = [0]*max(max(worker),max(difficulty)) # bfb[i] will tell us the best profitting job that is at or below difficulty i+1
        for diff,prof in sorted(zip(difficulty,profit)):
            bfb[diff-1] = max(bfb[diff-1],prof)
        
        currMax = 0
        for i in range(len(bfb)):
            bfb[i] = max(currMax,bfb[i])
            currMax = bfb[i]
            
        # print(bfb)
        
        total = 0
        for w in worker:
            total += bfb[w-1]
            
        return total

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
            difficulty_price = sorted(list(zip(difficulty, profit)), key = lambda x: (x[0], x[1]))    
            max_prices = []
            n = -1
            curr_price = 0
            for i in range(max(difficulty)+1):
                if i == difficulty_price[n+1][0]:
                    n+=1
                    while n < len(difficulty_price) - 1 and i == difficulty_price[n+1][0]:
                        n+=1
                    if difficulty_price[n][1] > curr_price:
                        curr_price = difficulty_price[n][1]
                max_prices.append(curr_price)
            profit_sum = 0
            for sub_worker in worker:
                if sub_worker >= len(max_prices):
                    profit_sum += max_prices[-1]
                else:
                    profit_sum += max_prices[sub_worker]
            return profit_sum

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        #get best profit by difficulty and apply to each worker
        #init memo table
        m = max(difficulty)
        dp = [0] * m
        for d, p in zip(difficulty, profit):
            dp[d - 1] = max(dp[d - 1], p) 
        for i in range(1,len(dp)):
            dp[i] = max(dp[i], dp[i - 1])    
        return sum([dp[min(w - 1, m - 1)] for w in worker])    


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = list(zip(difficulty, profit))
        jobs.sort()
        ans = i = best = 0
        for skill in sorted(worker):
            while i < len(jobs) and skill >= jobs[i][0]:
                best = max(best, jobs[i][1])
                i += 1
            ans += best
        return ans

class Solution:
  def binarySearch(self, l, r, x, li):
    if (r - l <= 1):
      if (li[r] <= x):
          return r
      else:
          return l
    m = (l + r + 1)//2
    if (li[m] <= x):
      return self.binarySearch(m, r, x, li)
    else:
      return self.binarySearch(l, m-1, x, li)
      
  def maxProfitAssignment(self, difficulty, profit, worker):
    difficulty.append(0)
    profit.append(0)
    jobs = sorted(zip(difficulty, profit))
    J = len(jobs)
    jobDifficulty = [j[0] for j in jobs]
    mostProfit = [jobs[0][1] for j in jobs]
    for i in range(1, J):
      mostProfit[i] = max(jobs[i][1], mostProfit[i-1])
    totProfit = 0
    for w in worker:
      maxJob = self.binarySearch(0, J-1, w, jobDifficulty)
      totProfit += mostProfit[maxJob]
    return totProfit

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        n = len(profit)
        maxm = max(difficulty)
        dp = [0]*(1+maxm)
        
        for i in range(n):
            dp[difficulty[i]] = max(dp[difficulty[i]],profit[i])
        
        for i in range(1,maxm+1):
            dp[i] = max(dp[i],dp[i-1])
        
        ans = 0
        
        for i in worker:
            if i > maxm:
                ans += dp[maxm]
            else:
                ans += dp[i]
        return ans

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        max_v = max(max(difficulty), max(worker))
        
        n = len(difficulty)
        best = {}
        for i in range(n):
            d = difficulty[i]
            p = profit[i]
            if d not in best:
                best[d] = p
            else:
                best[d] = max(best[d], p)
        
        dp = [0] * (max_v + 1)
        dp[0] = 0
        for i in range (max_v + 1):
            p = 0
            if i in best:
                p = best[i]
            dp[i] = max(dp[i - 1], p)
        
        s = 0 
        for d in worker:
            s += dp[d]
        return s

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        dp_dict = dict(list(zip(difficulty, profit)))
        l = len(difficulty)
        for idx in range(l):
            d = difficulty[idx]
            if profit[idx] > dp_dict[d]:
                dp_dict[d] = profit[idx]
        dp_items = sorted(list(dp_dict.items()), key=lambda x: x[0])
        darr = [x[0] for x in dp_items]

        max_p = 0
        parr = list()
        for d,p in dp_items:
            if p > max_p:
                max_p = dp_dict[d]
            parr.append(max_p)

        ret = 0

        def get_nearest(w, arr):
            l = len(arr)
            if w < arr[0]: return None
            if w > arr[-1]: return l-1

            def binary_search(w, i, j):
                if i >= l or j >= l or w < arr[i] or w > arr[j]:
                    return None
                if w == arr[i]: return i
                if w == arr[j]: return j
                k = (i + j) // 2
                if arr[k] <= w < arr[k + 1]:
                    return k
                prev = binary_search(w, i, k)
                return binary_search(w, k + 1, j) if prev is None else prev

            return binary_search(w, 0, l - 1)

        for w in worker:
            floor_idx = get_nearest(w, darr)
            if floor_idx is not None:
                ret += parr[floor_idx]
        return ret


from typing import List
import heapq
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        # (-profit[i], difficulty[i])组成最小堆
        result_profit = 0
        profit_minus_min_heap = list()
        for i in range(len(profit) ):
            heapq.heappush(profit_minus_min_heap, (-profit[i], difficulty[i]) )
        worker_minus_min_heap = [-worker[i] for i in range( len(worker) )]
        heapq.heapify(worker_minus_min_heap)

        while len(worker_minus_min_heap)!=0  and len(profit_minus_min_heap)!=0:
            job_profit, job_difficulty = profit_minus_min_heap[0]
            job_profit = -job_profit
            worker_ability = worker_minus_min_heap[0]
            worker_ability = -worker_ability
            if worker_ability >= job_difficulty:
                result_profit += job_profit
                heapq.heappop( worker_minus_min_heap)
            else:
                heapq.heappop( profit_minus_min_heap)
        
        return result_profit

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        make=[0]*(10**5)
        num=[(difficulty[i],profit[i])for i in range(len(profit))]
        num.sort(key=lambda x:x[0])
        x=0
        while x<len(num):
            if x+1<len(num):
                if num[x][1]>num[x+1][1]:
                    num.pop(x+1)
                else:x+=1
            else:break
        for i in range(len(num)):
            make[num[i][0]]=num[i][1]
        pre=-1
        for i in range(len(make)):
            if make[i]!=0:
                pre=make[i]
            elif pre!=-1:
                make[i]=pre
##        print(make)
        ans=0
        
        for w in worker:
            ans+=make[w]
        return ans


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        make=[0]*(10**5)
        num=[(difficulty[i],profit[i])for i in range(len(profit))]
        num.sort(key=lambda x:x[0])
        x=0
        while x<len(num):
            if x+1<len(num):
                if num[x][1]>num[x+1][1]:
                    num.pop(x+1)
                else:x+=1
            else:break
        for i in range(len(num)):
            make[num[i][0]]=num[i][1]
        pre=-1
        for i in range(len(make)):
            if make[i]!=0:
                pre=make[i]
            elif pre!=-1:
                make[i]=pre
        ans=0
        for w in worker:
            ans+=make[w]
        return ans    


import numpy as np
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        direc = np.zeros((len(profit),2))
        direc[:,0] = difficulty
        direc[:,1] = profit
        direc = direc[direc[:,0].argsort()]
        # print(direc)
        max_profit = np.array(direc[:,1])
        for i in range(1,len(profit)):
            if max_profit[i-1] > direc[i,1]:
                max_profit[i] = max_profit[i-1]
        # print(max_profit)
        result = 0
        for j in range(len(worker)):
            # if worker[j] in difficulty:
            #     ind = np.searchsorted(direc[:,0],worker[j],side = 'Left')
            # else: ind = np.searchsorted(direc[:,0],worker[j],side = 'Left') - 1
            ind = np.searchsorted(direc[:,0],worker[j],side = 'Right') - 1
            # print(ind,max_profit[ind])
            if ind >-1:result += max_profit[ind]
        return int(result)