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]

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Amortized analysis

Data structures

Greedy algorithms

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)
		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


from queue import PriorityQueue

class Solution:

	def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
		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
		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])
		ans = 0
		for i in worker:
			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
		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
		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
		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:
			while jobIndex < len(job):
				if job[jobIndex][0] <= workerCab:
					break
				else:
					jobIndex += 1
			if jobIndex < len(job):
				output = output + job[jobIndex][1]
		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])
		(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 = {}
		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
		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]
			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
			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]
		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
			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: 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
		for w in worker:
			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:

		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)):
			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])
		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


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, 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
		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:
		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, 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:

		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


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:
		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]
		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_diff = max(difficulty)
		max_profits = [0] * (max_diff + 1)
		for (diff, profit) in zip(difficulty, profit):
			max_profits[diff] = max(max_profits[diff], profit)
		for i in range(1, max_diff + 1):
			max_profits[i] = max(max_profits[i], max_profits[i - 1])
		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


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:
		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
			total += best_profit
		return total


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:
		bfb = [0] * max(max(worker), max(difficulty))
		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]
		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:
		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 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:
		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:
		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
		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()]
		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]
		result = 0
		for j in range(len(worker)):
			ind = np.searchsorted(direc[:, 0], worker[j], side='Right') - 1
			if ind > -1:
				result += max_profit[ind]
		return int(result)