There are N workers.  The i-th worker has a quality[i] and a minimum wage expectation wage[i].
Now we want to hire exactly K workers to form a paid group.  When hiring a group of K workers, we must pay them according to the following rules:

Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
Every worker in the paid group must be paid at least their minimum wage expectation.

Return the least amount of money needed to form a paid group satisfying the above conditions.
 



Example 1:
Input: quality = [10,20,5], wage = [70,50,30], K = 2
Output: 105.00000
Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.


Example 2:
Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
Output: 30.66667
Explanation: We pay 4 to 0-th worker, 13.33333 to 2-th and 3-th workers seperately. 

 
Note:

1 <= K <= N <= 10000, where N = quality.length = wage.length
1 <= quality[i] <= 10000
1 <= wage[i] <= 10000
Answers within 10^-5 of the correct answer will be considered correct.

Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms
Skill types: Sorting

Data structures

Greedy algorithms

Starter code:
class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        

Solutions:
from typing import *
from heapq import heappop, heappush

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		N = len(quality)
		heap_quality = []
		workers = [i for i in range(N)]
		workers = sorted(workers, key=lambda x: wage[x] / quality[x])
		sum_quality = 0
		for i in range(K):
			heappush(heap_quality, -quality[workers[i]])
			sum_quality += quality[workers[i]]
		ans = sum_quality * (wage[workers[K - 1]] / quality[workers[K - 1]])
		for i in range(K, N):
			heappush(heap_quality, -quality[workers[i]])
			sum_quality += quality[workers[i]]
			sum_quality += heappop(heap_quality)
			ans = min(ans, sum_quality * (wage[workers[i]] / quality[workers[i]]))
		return ans


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		workers = sorted(([float(w) / q, q] for (w, q) in zip(wage, quality)))
		res = float('inf')
		qsum = 0
		heap = []
		for (r, q) in workers:
			heapq.heappush(heap, -q)
			qsum += q
			if len(heap) > K:
				qsum += heapq.heappop(heap)
			if len(heap) == K:
				res = min(res, qsum * r)
		return res


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		from fractions import Fraction
		workers = sorted(((Fraction(w, q), q, w) for (q, w) in zip(quality, wage)))
		ans = float('inf')
		pool = []
		sumq = 0
		for (ratio, q, w) in workers:
			heapq.heappush(pool, -q)
			sumq += q
			if len(pool) > K:
				sumq += heapq.heappop(pool)
			if len(pool) == K:
				ans = min(ans, ratio * sumq)
		return float(ans)


import heapq

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		n_workers = len(wage)
		pairs = [None] * n_workers
		for i in range(n_workers):
			pairs[i] = (quality[i], wage[i] / quality[i])
		pairs = sorted(pairs, key=lambda x: x[1])
		sum_q = sum([p[0] for p in pairs[0:K]])
		maxheap_q = [-p[0] for p in pairs[0:K]]
		heapq.heapify(maxheap_q)
		min_cost = sum_q * pairs[K - 1][1]
		for i in range(K, n_workers):
			sum_q = sum_q - -min(maxheap_q) + pairs[i][0]
			min_cost = min(min_cost, sum_q * pairs[i][1])
			heapq.heapreplace(maxheap_q, -pairs[i][0])
		return min_cost


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		ratios = [[wi / qi, qi] for (wi, qi) in zip(wage, quality)]
		ratios.sort(reverse=True)
		res = float('inf')
		quality.sort()
		for (ratio, q) in ratios:
			quality.remove(q)
			candidates = quality[:K - 1]
			if len(candidates) < K - 1:
				break
			ans = ratio * (q + sum(candidates))
			res = min(res, ans)
		return res


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		extra_worker_heap = list()
		for i in range(len(quality)):
			heappush(extra_worker_heap, (wage[i] / quality[i], quality[i]))
		hired_worker_heap = list()
		hired_quality = 0
		wage_to_quality = 0
		min_cost = 10000000000.0
		while extra_worker_heap:
			(cur_wage_to_quality, worker_quality) = heappop(extra_worker_heap)
			hired_quality += worker_quality
			heappush(hired_worker_heap, -worker_quality)
			while len(hired_worker_heap) > K:
				hired_quality += heappop(hired_worker_heap)
			if len(hired_worker_heap) == K:
				min_cost = min(min_cost, hired_quality * cur_wage_to_quality)
		return min_cost


from heapq import *

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		workers = []
		for i in range(len(quality)):
			workers.append([wage[i] / quality[i], wage[i], quality[i]])
		workers = sorted(workers, key=lambda x: [x[0], x[2], x[1]])
		cost = math.inf
		maxHeap = []
		tot = 0
		for (r, w, q) in workers:
			heappush(maxHeap, -q)
			tot += q
			if len(maxHeap) > K:
				tot += heappop(maxHeap)
			if len(maxHeap) == K:
				cost = min(cost, r * tot)
		return float(cost)


import heapq

class Solution:

	def mincostToHireWorkers(self, quality, wage, K: int) -> float:
		workers = sorted([[w / q, q, w] for (q, w) in zip(quality, wage)])
		res = float('inf')
		pool = []
		sumq = 0
		for (r, q, w) in workers:
			heappush(pool, -q)
			sumq += q
			if len(pool) > K:
				a = heappop(pool)
				sumq += a
			if len(pool) == K:
				res = min(res, r * sumq)
		return res


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		workers = sorted(([float(w) / q, q] for (w, q) in zip(wage, quality)))
		ans = float('inf')
		heap = []
		heapSum = 0
		for (ratio, q) in workers:
			heapq.heappush(heap, -q)
			heapSum += q
			if len(heap) > K:
				heapSum += heapq.heappop(heap)
			if len(heap) == K:
				ans = min(ans, ratio * heapSum)
		return float(ans)


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		employees = sorted([[w / q, q] for (w, q) in zip(wage, quality)])
		print(employees)
		(res, totalOut) = (math.inf, 0)
		h = []
		for (rate, output) in employees:
			totalOut += output
			heapq.heappush(h, -output)
			if len(h) > K:
				totalOut += heapq.heappop(h)
			if len(h) == K:
				res = min(res, totalOut * rate)
		return res


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		ratio = sorted(((w / q, q) for (w, q) in zip(wage, quality)))
		h = []
		(s, res) = (0, float('inf'))
		for (r, q) in ratio:
			heapq.heappush(h, -q)
			s += q
			if len(h) > K:
				s += heapq.heappop(h)
			if len(h) == K:
				res = min(res, r * s)
		return res


import heapq

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		minHeap = []
		maxHeap = []
		zipped = list(zip(wage, quality))
		zipped = sorted(zipped, key=lambda x: x[0] / x[1])
		minCost = float('inf')
		totalQuality = 0
		for i in range(len(zipped)):
			curRatio = zipped[i][0] / zipped[i][1]
			if len(minHeap) < K:
				heapq.heappush(minHeap, (-zipped[i][1], zipped[i][0]))
				totalQuality += zipped[i][1]
			else:
				heapq.heappush(maxHeap, (zipped[i][1], zipped[i][0]))
				while curRatio * maxHeap[0][0] < curRatio * minHeap[0][0] * -1:
					maxTop = heapq.heappop(maxHeap)
					minTop = heapq.heappop(minHeap)
					heapq.heappush(minHeap, (-maxTop[0], maxTop[1]))
					heapq.heappush(maxHeap, (-minTop[0], minTop[1]))
					totalQuality = totalQuality + minTop[0]
					totalQuality += maxTop[0]
			if len(minHeap) == K and totalQuality * curRatio < minCost:
				minCost = totalQuality * curRatio
		return minCost


from heapq import *

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		N = len(quality)
		workers = [(wage[i] / float(quality[i]), quality[i]) for i in range(N)]
		workers = sorted(workers)
		result = float('inf')
		sum_ = 0
		max_heap = []
		for i in range(K - 1):
			heappush(max_heap, -workers[i][1])
			sum_ += workers[i][1]
		for i in range(K - 1, len(workers)):
			result = min(result, (sum_ + workers[i][1]) * workers[i][0])
			if len(max_heap) > 0 and workers[i][1] < -max_heap[0]:
				sum_ -= -heappop(max_heap)
				sum_ += workers[i][1]
				heappush(max_heap, -workers[i][1])
		return result


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		workers = []
		for (q, w) in zip(quality, wage):
			workers.append((w / q, q, w))
		workers.sort()
		ans = float('inf')
		dui = []
		sumq = 0
		for (ratio, q, w) in workers:
			heapq.heappush(dui, -q)
			sumq += q
			if len(dui) > K:
				sumq = sumq + heapq.heappop(dui)
			if len(dui) == K:
				ans = min(ans, ratio * sumq)
		return ans


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		wq = sorted([(a / b, b) for (a, b) in zip(wage, quality)])
		res = float('inf')
		heap = []
		qSum = 0
		for (avg, q) in wq:
			qSum += q
			heapq.heappush(heap, -q)
			if len(heap) > K:
				qSum += heapq.heappop(heap)
			if len(heap) == K:
				res = min(res, avg * qSum)
		return res


import heapq

class Solution:

	def mincostToHireWorkers_tle(self, quality: List[int], wage: List[int], K: int) -> float:
		ans = float('inf')
		for i in range(len(quality)):
			factor = wage[i] / quality[i]
			prices = []
			for i in range(len(quality)):
				if factor * quality[i] >= wage[i]:
					prices.append(factor * quality[i])
			if len(prices) < K:
				continue
			prices.sort()
			ans = min(ans, sum(prices[:K]))
		return ans

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		if not quality:
			return 0
		workers = sorted([(wage[i] / quality[i], quality[i], wage[i]) for i in range(len(quality))])
		min_cost = float('inf')
		total = 0
		k_workers = []
		for w in workers:
			total += w[1]
			heapq.heappush(k_workers, -w[1])
			if len(k_workers) > K:
				total += heapq.heappop(k_workers)
			if len(k_workers) == K:
				min_cost = min(min_cost, total * w[0])
		return min_cost


import heapq as hq

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		if K == 1:
			return min(wage)
		N = len(quality)
		ratio = [(w / q, i) for (i, (w, q)) in enumerate(zip(wage, quality))]
		ratio.sort()
		quality = [quality[i] for (_, i) in ratio]
		ratio = [r for (r, _) in ratio]
		min_K_queue = [-x for x in quality[:K - 1]]
		hq.heapify(min_K_queue)
		_sum = sum(quality[:K - 1])
		_min = float('inf')
		for k in range(K - 1, N):
			_min = min((_sum + quality[k]) * ratio[k], _min)
			if -quality[k] > min_K_queue[0]:
				hq.heappush(min_K_queue, -quality[k])
				poped = hq.heappop(min_K_queue)
				_sum = _sum + poped + quality[k]
		return _min


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		q_w = [(w / q, q, w) for (q, w) in zip(quality, wage)]
		q_w.sort()
		curr = sum([q_w[i][1] for i in range(K)])
		heap = [-q_w[i][1] for i in range(K)]
		heapq.heapify(heap)
		r = q_w[K - 1][0]
		res = r * curr
		for (r, q, w) in q_w[K:]:
			curr += q
			heapq.heappush(heap, -q)
			curr += heapq.heappop(heap)
			res = min(res, curr * r)
		return res


import heapq as pq

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		ratio = [[y / x, x] for (x, y) in zip(quality, wage)]
		ratio.sort(key=lambda x: x[0])
		i = 0
		l = []
		pq.heapify(l)
		r = 1
		s = 0
		while i < K:
			s += ratio[i][1]
			pq.heappush(l, -ratio[i][1])
			r = ratio[i][0]
			i += 1
		res = s * r
		n = len(quality)
		while i < n:
			r = ratio[i][0]
			num = ratio[i][1]
			pq.heappush(l, -num)
			val = -pq.heappop(l)
			s += num - val
			res = min(res, s * r)
			i += 1
		return res


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		A = []
		for (q, w) in zip(quality, wage):
			A.append([q, w / q])
		(pq, ans) = ([], float('inf'))
		(qSum, ratio) = (0, 0)
		for a in sorted(A, key=lambda x: x[1]):
			if len(pq) < K:
				heapq.heappush(pq, [-a[0], a[1]])
				qSum += a[0]
				ratio = a[1]
			else:
				negq = heapq.heappop(pq)[0]
				qSum = qSum + negq + a[0]
				ratio = a[1]
				heapq.heappush(pq, [-a[0], a[1]])
			if len(pq) == K:
				ans = min(ans, qSum * ratio)
		return ans


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		workers = sorted([(w / q, q, w) for (w, q) in zip(wage, quality)])
		print(workers)
		result = math.inf
		qualitySum = 0
		maxheap = []
		for (r, q, _) in workers:
			heapq.heappush(maxheap, -q)
			qualitySum += q
			if len(maxheap) > K:
				qualitySum += heapq.heappop(maxheap)
			if len(maxheap) == K:
				print((qualitySum * r, r, qualitySum))
				result = min(result, qualitySum * r)
		return result


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		n = len(quality)
		workers = sorted(([w / q, q] for (q, w) in zip(quality, wage)))
		que = []
		res = math.inf
		curQuality = 0
		for (ratio, q) in workers:
			heapq.heappush(que, -q)
			curQuality += q
			if len(que) > K:
				q2 = -heapq.heappop(que)
				curQuality -= q2
			if len(que) == K:
				res = min(res, curQuality * ratio)
		return res


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		return self.heap(quality, wage, K)

	def greedy(self, quality, wage, K):
		ans = float('inf')
		size = len(quality)
		for captain in range(size):
			ratio = wage[captain] / quality[captain]
			prices = []
			for worker in range(size):
				price = ratio * quality[worker]
				if price < wage[worker]:
					continue
				prices.append(price)
			if len(prices) < K:
				continue
			prices.sort()
			ans = min(ans, sum(prices[:K]))
		return float(ans)

	def heap(self, quality, wage, K):
		workers = sorted(((w / q, q, w) for (q, w) in zip(quality, wage)))
		ans = float('inf')
		myHeap = []
		qualitySum = 0
		for (ratio, q, w) in workers:
			heapq.heappush(myHeap, -q)
			qualitySum += q
			if len(myHeap) > K:
				qualitySum += heapq.heappop(myHeap)
			if len(myHeap) == K:
				ans = min(ans, ratio * qualitySum)
		return float(ans)


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		n = len(quality)
		wage_per_qual = []
		for i in range(n):
			wage_per_qual.append(wage[i] / quality[i])
		workers = sorted(list(range(n)), key=lambda i: wage_per_qual[i])
		max_heap = []
		total_quality = 0
		min_total = float('inf')
		for w in workers:
			if len(max_heap) < K:
				total_quality += quality[w]
				heapq.heappush(max_heap, -quality[w])
				if len(max_heap) == K:
					min_total = min(min_total, wage_per_qual[w] * total_quality)
			elif quality[w] < -max_heap[0]:
				neg_qual = heapq.heappushpop(max_heap, -quality[w])
				total_quality += neg_qual + quality[w]
				min_total = min(min_total, wage_per_qual[w] * total_quality)
		return min_total


from heapq import heappush, heappop

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		if len(wage) >= K:
			worker = []
			for i in range(0, len(quality)):
				rate = wage[i] / quality[i]
				worker.append((rate, quality[i]))
			worker.sort()
			base = 0
			i = 0
			q = []
			while i < K - 1:
				base += worker[i][1]
				heappush(q, -worker[i][1])
				i += 1
			res = (base + worker[i][1]) * worker[i][0]
			while i < len(worker):
				rate = worker[i][0]
				res = min(res, (base + worker[i][1]) * rate)
				heappush(q, -worker[i][1])
				base += worker[i][1]
				val = heappop(q)
				base += val
				i += 1
			return res
		else:
			return -1.0


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		workers = [(wage / quality, wage, quality) for (wage, quality) in zip(wage, quality)]
		workers.sort(key=lambda x: x[0])
		heap = []
		quality_sum = 0
		final_cost = float('inf')
		for (ratio, wage, quality) in workers:
			heapq.heappush(heap, -1 * quality)
			quality_sum += quality
			if len(heap) > K:
				q = heapq.heappop(heap)
				quality_sum += q
			if len(heap) == K:
				cost = ratio * quality_sum
				final_cost = min(final_cost, cost)
		return final_cost


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		x = sorted(((wage / quality, wage, quality) for (wage, quality) in zip(wage, quality)))
		cur_sum = 0
		heap = []
		res = sys.maxsize
		for (r, w, q) in x:
			heapq.heappush(heap, -q)
			cur_sum += q
			if len(heap) > K:
				cur_sum += heapq.heappop(heap)
			if len(heap) == K:
				res = min(res, cur_sum * r)
		return res


from queue import PriorityQueue

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		ratios = [w / q for (w, q) in zip(wage, quality)]
		workers = [(r, q, w) for (r, q, w) in zip(ratios, quality, wage)]
		workers = sorted(workers)
		pQueue = PriorityQueue()
		min_quality_sum = 0.0
		cost = float('inf')
		for (r, q, w) in workers:
			pQueue.put(-q)
			min_quality_sum = min_quality_sum + q
			if pQueue.qsize() > K:
				max_quality = pQueue.get()
				min_quality_sum = min_quality_sum + max_quality
			if pQueue.qsize() == K:
				new_cost = r * min_quality_sum
				if new_cost < cost:
					cost = new_cost
		return cost


from decimal import Decimal

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		workers = [(Decimal(wage[i] / quality[i]), quality[i]) for i in range(len(wage))]
		heapq.heapify(workers)
		(res, unit_price, total_quality, heap) = (float('inf'), -1.0, 0, [])
		while workers:
			(u, q) = heapq.heappop(workers)
			unit_price = max(u, unit_price)
			heapq.heappush(heap, -q)
			total_quality += q
			if len(heap) > K:
				total_quality += heapq.heappop(heap)
			if len(heap) == K:
				res = min(res, total_quality * unit_price)
		return res


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		from fractions import Fraction
		workers = sorted([(w / q, q, w) for (q, w) in zip(quality, wage)])
		min_cost = float('inf')
		from queue import PriorityQueue
		pq = PriorityQueue()
		summ = 0
		print(workers)
		for (ratio, q, w) in workers:
			pq.put(-q)
			summ += q
			if pq.qsize() > K:
				summ += pq.get()
			if pq.qsize() == K:
				min_cost = min(min_cost, ratio * summ)
		return float(min_cost)


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		ratios = [(wi / qi, qi) for (wi, qi) in zip(wage, quality)]
		ratios.sort()
		res = float('inf')
		pq = []
		cur = 0
		for (i, (ratio, q)) in enumerate(ratios):
			if i >= K - 1:
				res = min(res, ratio * (q + cur))
			cur += q
			heapq.heappush(pq, -q)
			if len(pq) > K - 1:
				cur += heapq.heappop(pq)
		return res


class Solution:

	def mincostToHireWorkers(self, quality, wage, K):
		workers = sorted(([float(w) / q, q] for (w, q) in zip(wage, quality)))
		res = float('inf')
		qsum = 0
		heap = []

		def rec(l, r, heap, newQ):
			if l > r:
				heap.insert(l, newQ)
				return heap
			m = l + int((r - l) / 2)
			if heap[m] > newQ:
				return rec(l, m - 1, heap, newQ)
			else:
				return rec(m + 1, r, heap, newQ)
		for (r, q) in workers:
			heap = rec(0, len(heap) - 1, heap, q)
			qsum += q
			if len(heap) > K:
				p = heap.pop(K)
				qsum += -p
			if len(heap) == K:
				res = min(res, qsum * r)
		return res


class Solution(object):

	def mincostToHireWorkers(self, quality, wage, K):
		workers = sorted(((w / q, q, w) for (q, w) in zip(quality, wage)))
		print(workers)
		ans = float('inf')
		pool = []
		sumq = 0
		for (ratio, q, w) in workers:
			heapq.heappush(pool, -q)
			sumq += q
			if len(pool) > K:
				sumq += heapq.heappop(pool)
			if len(pool) == K:
				ans = min(ans, ratio * sumq)
		return float(ans)


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		combine = sorted([(wage[i] / quality[i], quality[i]) for i in range(len(quality))], key=lambda x: (-x[0], x[1]))
		tc = float('inf')
		n = len(combine)
		q = []
		heapq.heapify(q)
		for i in range(len(combine) - 1, -1, -1):
			heapq.heappush(q, -combine[i][1])
			if len(q) > K:
				heapq.heappop(q)
			if i <= n - K:
				tc = min(tc, -combine[i][0] * sum(q))
		return tc


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		ratios = [(w / q, i) for (i, (q, w)) in enumerate(zip(quality, wage))]
		ratios.sort()
		heap = []
		sumq = 0
		ans = math.inf
		for (ratio, i) in ratios:
			sumq += quality[i]
			heapq.heappush(heap, -quality[i])
			if len(heap) > K:
				q = heapq.heappop(heap)
				sumq += q
			if len(heap) == K:
				ans = min(ans, sumq * ratio)
		return ans


from heapq import heappush, heappop

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		from fractions import Fraction
		cap_wage = sorted(((Fraction(w, q), q, w) for (q, w) in zip(quality, wage)))
		cap_wage = sorted([(w / c, c, w) for (c, w) in zip(quality, wage)])
		heap = []
		re = float('inf')
		val = 0
		for (ratio, c, w) in cap_wage:
			heappush(heap, -c)
			val += c
			if len(heap) > K:
				val += heappop(heap)
			if len(heap) == K:
				re = min(re, val * ratio)
		return float(re)


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		from fractions import Fraction
		workers = sorted(((Fraction(w, q), q, w) for (q, w) in zip(quality, wage)))
		min_val = float('Inf')
		pool = []
		sum_q = 0
		for (r, q, w) in workers:
			heapq.heappush(pool, -q)
			sum_q += q
			if len(pool) > K:
				sum_q += heapq.heappop(pool)
			if len(pool) == K:
				min_val = min(min_val, r * sum_q)
		return min_val


from heapq import heappush, heappop
from fractions import Fraction

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		workers = [(Fraction(w, q), q, w) for (w, q) in zip(wage, quality)]
		workers.sort()
		best = float('inf')
		queue = []
		sumq = 0
		for (ratio, q, w) in workers:
			heappush(queue, -q)
			sumq += q
			if len(queue) > K:
				sumq += heappop(queue)
			if len(queue) == K:
				best = min(best, ratio * sumq)
		return best


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		from fractions import Fraction
		wage_qual = sorted(((Fraction(w, q), w, q) for (w, q) in zip(wage, quality)))
		candidates = []
		psum = 0
		ans = float('inf')
		for (ratio, w, q) in wage_qual:
			heapq.heappush(candidates, -q)
			psum += q
			if len(candidates) < K:
				continue
			elif len(candidates) > K:
				psum += heapq.heappop(candidates)
			ans = min(ans, psum * ratio)
		return ans


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		from fractions import Fraction
		workers = sorted(((Fraction(w, q), q, w) for (q, w) in zip(quality, wage)))
		ans = float('inf')
		pool = []
		sumq = 0
		for (ratio, q, w) in workers:
			heapq.heappush(pool, -q)
			sumq += q
			if len(pool) > K:
				sumq += heapq.heappop(pool)
			if len(pool) == K:
				ans = min(ans, ratio * sumq)
		return float(ans)
		n = len(wage)
		if K > n:
			return float(0)
		re = []
		re.append(float('inf'))
		self.util(quality, wage, 0, [], K, re)
		return re[0]

	def util(self, q, w, i, p, k, re):
		if len(p) == k:
			s = sum([t[1] for t in p])
			if s < re[0]:
				re[0] = s
		if i == len(w):
			return
		self.util(q, w, i + 1, [x[:] for x in p], k, re)
		if not p:
			p.append([q[i], w[i]])
			self.util(q, w, i + 1, [x[:] for x in p], k, re)
		else:
			price = p[0][1] * q[i] / p[0][0]
			if price > w[i]:
				p.append([q[i], price])
				self.util(q, w, i + 1, [x[:] for x in p], k, re)
			else:
				for idx in p:
					idx[1] = w[i] * idx[0] / q[i]
				p.append([q[i], w[i]])
				self.util(q, w, i + 1, [x[:] for x in p], k, re)


from fractions import Fraction
from heapq import *

class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		workers = sorted(((Fraction(w, q), q, w) for (q, w) in zip(quality, wage)))
		result = float('inf')
		maxheap = []
		current_sum = 0
		for (ratio, q, w) in workers:
			heappush(maxheap, -q)
			current_sum += q
			if len(maxheap) > K:
				current_sum += heappop(maxheap)
			if len(maxheap) == K:
				result = min(result, ratio * current_sum)
		return float(result)


class Solution:

	def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
		from fractions import Fraction
		workers = sorted(((Fraction(w, q), q, w) for (q, w) in zip(quality, wage)))
		ans = float('inf')
		heap = []
		heapSum = 0
		for (ration, q, w) in workers:
			heapq.heappush(heap, -q)
			heapSum += q
			if len(heap) > K:
				heapSum += heapq.heappop(heap)
			if len(heap) == K:
				ans = min(ans, ration * heapSum)
		return float(ans)