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

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)  # negative quality value
            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)

class Solution(object):
    def mincostToHireWorkers(self, quality, wage, K):
        from fractions import Fraction
        workers = sorted((Fraction(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:
        from fractions import Fraction
        workers = sorted((Fraction(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)
            #print(pool)
            sumq += q

            if len(pool) > K:
                sumq += heapq.heappop(pool)
                #print(pool)

            if len(pool) == K:
                ans = min(ans, ratio * sumq)
                #print(sumq)
                #print(pool)

        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 # (quality, wage/quality) 
        for i in range(n_workers): 
            pairs[i] = (quality[i], wage[i]/quality[i])

        pairs = sorted(pairs, key=lambda x: (x[1])) # sort dec by ratio then quality 
        
        # incorrect solution
        # max_q = pairs[i:i+K]
        # for i in range(n_workers-K+1):
            # min_cost = min(min_cost, self.cost(pairs[i:i+K]))
        
        sum_q = sum([p[0] for p in pairs[0:K]])
        maxheap_q = [-p[0] for p in pairs[0:K]] # use minus to create max heap
        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])
            # print(sum_q * pairs[i][1])
            
        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 = 1e10
        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)
        
            


class Solution(object):
    def mincostToHireWorkers(self, quality, wage, K):
        from fractions import Fraction
        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)

import heapq

class Solution:
    def mincostToHireWorkers(self, quality, wage, K: int) -> float:
        # consider with min coefficient
        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:
            # candidates with maximaml quality first
            heappush(pool, -q)
            sumq += q
            if len(pool) > K:
                # remove redundant
                a = heappop(pool)
                sumq += a # subtract a from sum
            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:
        
        # sorting workers based on the ration of wage and quality
        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) # max heap based off quality
            heapSum += q
            
            if len(heap) > K:# if len of heap > K add largest heap elem
                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) #reduce q by removed employee - highest contribution first
            if len(h) == K:
                res = min(res, totalOut * rate) #worst rate in candidates * output for candidates
            
        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])
        #print(zipped)
        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)
        
        # sum_ = sum([x[1] for x in prices_per_unit[:K - 1]])
        
        # print(prices_per_unit)
        
        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 = 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:
        workers = sorted([(w/q, q) for q, w in zip(quality, wage)])
        heap = []
        sumq = 0
        res = float('inf')
        
        for r, q in workers:
            heapq.heappush(heap, -q)
            sumq += q
            
            if len(heap)>K:
                sumq += heapq.heappop(heap)
                
            if len(heap)==K:
                res = min(res, sumq*r)
        
        return res

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

        #计算最低工资/工作质量的比值；用一个堆维护K个工作质量最低的工作人员

        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:
                #去掉一个最高的quality
                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:
        # rate, q, w
        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 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]:
                poped = hq.heappop(min_K_queue)
                _sum = _sum + poped + quality[k]
                hq.heappush(min_K_queue, -quality[k])
        return _min
            


import heapq
class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        n_workers = len(wage)
        pairs = [None]*n_workers # (quality, ratio) 
        for i in range(n_workers): 
            pairs[i] = (quality[i], wage[i]/quality[i])

        pairs = sorted(pairs, key=lambda x: (x[1])) # sort dec by ratio 
        
        # ...incorrect solution...
        # max_q = pairs[i:i+K]
        # for i in range(n_workers-K+1):
            # min_cost = min(min_cost, self.cost(pairs[i:i+K]))
        
        sum_q = sum([p[0] for p in pairs[0:K]])
        maxheap_q = [-p[0] for p in pairs[0:K]] # use minus to create max heap
        heapq.heapify(maxheap_q) 
        min_cost = sum_q * pairs[K-1][1]
        
        for i in range(K, n_workers):
            sum_q = sum_q - (-heapq.heappop(maxheap_q)) + pairs[i][0]
            min_cost = min(min_cost, sum_q * pairs[i][1])
            heapq.heappush(maxheap_q, -pairs[i][0]) # push minus value to max heap
            
        return min_cost


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:
        workers = sorted([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

import heapq
class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        heap=[]
        rate=sorted(((w/q, q) for w, q in zip(wage, quality)))
        qsum=0
        res=float('inf')
        for r, q in rate:
            heapq.heappush(heap, -q)
            qsum+=q
            if len(heap)>K:
                qsum+=heapq.heappop(heap)
            if len(heap)==K:
                res=min(res, r*qsum)
        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)  #add because its maxheap and we had entered negative, so in theory this line subtracts
            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.greedy(quality, wage, K)
        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)

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


class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        n = len(quality)
        
        # 1. compute wage per quality for each worker i
        wage_per_qual = []
        for i in range(n):
            wage_per_qual.append(wage[i] / quality[i])
        
        # 2. sort wage per quality (sort worker index)
        workers = sorted(list(range(n)), key=lambda i: wage_per_qual[i])
        
        # 3. max heap keep track of minimum k quality
        max_heap = []
        # current total quality so far
        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)
            else:
                if quality[w] < -max_heap[0]:
                    neg_qual = heapq.heappushpop(max_heap, -quality[w])
                    total_quality += neg_qual + quality[w]
                    # # pop the maximum quality to add current worker
                    # neg_qual = heapq.heappop(max_heap)
                    # # remove previous max quality
                    # total_quality += neg_qual
                    # # add current quality
                    # total_quality += quality[w]
                    # heapq.heappush(max_heap, -quality[w])
                    
                    # use current worker as the base wage
                    min_total = min(min_total, wage_per_qual[w]*total_quality)
        
        return min_total


#Jenny 20201002
#sample 180 ms submission

# 857. Minimum Cost to Hire K Workers

import heapq 

class Solution: 
    # time O(nlogn), space O(n)
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        # 团队开销= 最低效人的 w/q * 团队总 q
        # 开除当前团队最低效的人
        # 引进待选集合中quality最小的人。
        workers = sorted((w/q, w, q) for w, q in zip(wage, quality))
        ans = float('inf')
        pool = []
        sum_q = 0
        
        for (ratio, w, q) in workers:
            heapq.heappush(pool, -q)
            sum_q += q
            
            if len(pool) > K:
                sum_q += heapq.heappop(pool)
            
            if len(pool) == K:
                ans = min(ans, ratio * sum_q)
                
            # print(sum_q, ans)
        return float(ans)


class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        '''
1- expect[i] = wage[i]/quality[i]: meaning i-th worker claims expect[i] money per each unit of its quality. Therefore, if expect[i] > expect[j], that means if we pay j-th worker quality[j]*expect[i] he/she would be more than happy and it's more than its minimal requested wage.

2- Therefore, for k workers sorted by their expect values, if we pay each worker q[i]*expect[k], both rules are satisfied. The total needed money = (sum(q_1 + q_2 + ... + q_k) * expect[k]). Note that this is the minimum money for this k workers, since you have to pay the k-th worker at least q[k]*expect[k]. This part is very tricky, think of this in contrary, if you don't pay each of K workers with expected[k], let's say if you pick expected[k-1], you will not satisfy kth worker. So, the minimum expected pay per quality is expected[k] to satisfy all k workers. Every worker is paid in terms of quality ratio so we come up with a common pay per quality. 

3- To recap, we sort workers based on their expect values. Say we are at worker i and want to form a k-group and we already know it would cost sum*expect[i]. To pay the minimum money we should minimize the sum, which can be found using a maxHeap (to replace the max value with a smaller one) to keep the smaller q's as we move forward.
        
        '''
        workers = sorted([float(w) / q, q] for w, q in zip(wage, quality))
        maxHeap = []
        res = float('inf')
        qsum = 0
        for expect, q in workers:
            qsum += q
            heapq.heappush(maxHeap, -q)
            if len(maxHeap) > K:
                qsum += heapq.heappop(maxHeap)
            if len(maxHeap) == K:
                res = min(res, expect*qsum)
        return res
            


import numpy as np
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))
        # print(workers)
        res = float('inf')
        qsum = 0
        heap = []
        for r, q in workers:
            # print(\"*****r: \", r, \"q: \", q)
            heapq.heappush(heap, -q)
            qsum += q
            # print(\"sum:\", qsum)
            # print(heap)
            if len(heap) > K: 
                # print(\"popping from heap\")
                qsum += heapq.heappop(heap)
                # print(\"qsum: \", qsum)
            if len(heap) == K: 
                res = min(res, qsum * r)
                # print(\"min: \", res)
        return res
        


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
            # print(worker)
            res = (base + worker[i][1]) * worker[i][0]
            while i < len(worker):
                # print((worker[i][0], base, res))
                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:
        # length = len(quality)
        # value_orders = sorted(range(length), key=lambda k: wage[k] / quality[k])

        # worker_quality = []
        # minimum_cost = 0
        # for i in range(0, K):
        #     worker_quality.append(quality[value_orders[i]])
        #     minimum_cost += wage[value_orders[K - 1]] / quality[value_orders[K - 1]] * quality[value_orders[i]]

        # worker_quality.sort()
        # for i in range(K, length):
        #     if quality[value_orders[i]] < worker_quality[-1]:
        #         worker_quality.pop()
        #         worker_quality.append(quality[value_orders[i]])
        #         worker_quality.sort()
        #     this_round_cost = 0
        #     for q in worker_quality:
        #         this_round_cost += q * wage[value_orders[i]] / quality[value_orders[i]]
        #     minimum_cost = min(minimum_cost, this_round_cost)
        # return minimum_cost



        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)
                # adding rather than substracting, since quality is inserted as negative
                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)

        #heap = []
        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 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)
        
        # sum_ = sum([x[1] for x in prices_per_unit[:K - 1]])
        
        # print(prices_per_unit)
        
        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


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 we already hire K workers, we fire the worker with the highest quality
            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:

        #计算最低工资/工作质量的比值；用一个堆维护K个工作质量最低的工作人员

        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:
                #去掉一个最高的quality
                sumq=sumq+heapq.heappop(dui)

            if len(dui)==K:
                ans=min(ans,ratio*sumq)

        return float(ans)



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))
        #print('workers: ',workers)
        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:
            #print('before heap: ', heap)
            heap=rec(0,len(heap)-1,heap,q)
            #print('after heap: ', heap)
            qsum += q
            if len(heap) > K:
                
                p=heap.pop(K)
                #print('heapq.heappop(heap): ',p, 'r:', r, 'qsum: ',qsum)
                qsum += -p
            if len(heap) == K:
                res = min(res, qsum * r)
        return res

class Solution:
    def mincostToHireWorkers(self, quality, wage, K):
        workers = sorted([float(w) / q, q] for w, q in zip(wage, quality))
        print('workers: ',workers)
        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:
            #print('before heap: ', heap)
            heap=rec(0,len(heap)-1,heap,q)
            #print('after heap: ', heap)
            qsum += q
            if len(heap) > K:
                
                p=heap.pop(-1)
                #print('heapq.heappop(heap): ',p, 'r:', r, 'qsum: ',qsum)
                qsum += -p
            if len(heap) == K:
                res = min(res, qsum * r)
        return res

class Solution(object):
    def mincostToHireWorkers(self, quality, wage, K):
        #from fractions import Fraction
        #workers = sorted((Fraction(w, q), q, w)
        #                 for q, w in zip(quality, wage))
        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, wage, K):
        workers = sorted([float(w) / q, q] for w, q in zip(wage, quality))
        #print('workers: ',workers)
        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)
            
        L=0
        for r, q in workers:
            #print('before heap: ', heap)
            heap=rec(0,L-1,heap,q)
            L+=1
            #print('after heap: ', heap)
            qsum += q
            if L > K:
                
                p=heap.pop(K)
                L-=1
                #print('heapq.heappop(heap): ',p, 'r:', r, 'qsum: ',qsum)
                qsum += -p
            if len(heap) == K:
                res = min(res, qsum * r)
        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)
            
        L=0
        for r, q in workers:
            heap=rec(0,L-1,heap,q)
            L+=1
            qsum += q
            if L > K:
                
                p=heap.pop(K)
                L-=1
                qsum += -p
            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:
        combine =  sorted([(wage[i]/quality[i], quality[i]) for i in range(len(quality))] , key = lambda x: (-x[0], x[1]) )
        # qual = [e[1] for e in combine]
        # rates = [e[0] for e in combine]
        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:
        combine =  sorted([(wage[i]/quality[i], quality[i]) for i in range(len(quality))] , key = lambda x: (-x[0], x[1]) )
        # combine =  sorted([(quality[i],wage[i]/quality[i]) for i in range(len(quality))])
        qual = [e[1] for e in combine]
        rates = [e[0] for e in combine]
        tc = float('inf')
        n = len(combine)
        q = []
        heapq.heapify(q)
        for i in range(len(combine)-1,-1,-1):
            # if i < K-1: return tc
            heapq.heappush(q, -qual[i])
            if len(q) > K:
                heapq.heappop(q)
            if i <= n-K: 
                tc = min(tc, -rates[i]*sum(q))
            
        return tc


class Solution:
    def mincostToHireWorkers(self, quality, wage, K):
        workers = sorted([float(w) / q, q] for w, q in zip(wage, quality))
        #print('workers: ',workers)
        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:
            #print('before heap: ', heap)
            heap=rec(0,len(heap)-1,heap,q)
            #print('after heap: ', heap)
            qsum += q
            if len(heap) > K:
                
                p=heap.pop(-1)
                #print('heapq.heappop(heap): ',p, 'r:', r, 'qsum: ',qsum)
                qsum += -p
            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:
        
        ratios = [(w/q,i) for i,(q,w) in enumerate(zip(quality, wage))]
        ratios.sort()
        
        heap = [] # -q
        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 # q is negative
            if len(heap) == K:
                ans = min(ans, sumq*ratio)
        return ans
            
            
            
            
            # 7 2.5 6 


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)

class Solution(object):
    def mincostToHireWorkers(self, quality, wage, K):
        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)


from heapq import heappush, heappop
class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        #store capacity/wage
        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(object):
    def mincostToHireWorkers(self, quality, wage, K):
        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)

class Solution(object):
       
    
    def mincostToHireWorkers(self, quality, wage, K):
        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)

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))
        #print(workers)
        min_val = float('Inf')
        #print(min_val)
        
        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


class Solution(object):
       
    
    def mincostToHireWorkers(self, quality, wage, K):
        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)


# Idea is as follows: If workers are paid in ratio of their qualities, then w_j = (w_ref/q_ref) * q_j

# After paying in the above ratio, to ensure we pay workers their min wage, then we need to select the higher wage/ratio as reference among two possible wage/quality ratios 


# So if the size of array is k, then we just select the highest ratio and use that as ref, then 
#  min cost =  (highest ratio ) * (sum of all Qualities)

# or in other words, sort the wage to ratios in increasing order, then last one will be ref ration and this ref ratio times sumq = ans.

# now consider k+1 elements present. then same as above logic, if we sort the wage/quality ratios in increasing order, then any of the ratios from kth to later can be a candidate ref ratio. If k elements, we already know the ans is kth ratio * sumq. Now consider k+1 th element. We can have this as ref ration instead. Then which one would we remove to get k elements? We want to remove the element with highest quality as that would reduce the cost by max. (remember total cost = ref ratio * ( sum of qualities)). So we use max heap to maintain qualities and remove the highest quality when we consider all indexes > k. and among all those possible indexes k to n, we find which gives min cost.



class Solution(object):
#     def mincostToHireWorkers(self, quality, wage, k):
#         from fractions import Fraction
#         workers = sorted((Fraction(w, q), q, w)
#                          for q, w in zip(quality, wage))

#         maxRatio = workers[-1][0]
        
#         quality.sort()
#         sumq=sum(quality[:k])
#         return sumq*maxRatio
        
    
    def mincostToHireWorkers(self, quality, wage, K):
        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)

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

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, wage, K):
        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
        
        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 :
                psum += heapq.heappop(candidates)
            
            if len(candidates) == K :
                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)
                
                
                    
            
        
        
        
            


class Solution(object):
    def mincostToHireWorkers(self, quality, wage, K):
        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)
    
#     def mincostToHireWorkers(self, quality, wage, K):
#         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)


from fractions import Fraction
from heapq import *

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        
        # quality = [3,1,10,10,1]
        # wage = [4,8,2,2,7]
        # K = 3

        workers = sorted((Fraction(w, q), q, w) for q, w in zip(quality, wage))
        
        # print(workers)

        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)

            # print(ratio, q, w, maxheap,current_sum,result)
        
        return float(result)        


#         from fractions import Fraction
#         ans = float('inf')

#         N = len(quality)
#         for captain in range(N):
#             # Must pay at least wage[captain] / quality[captain] per qual
#             factor = Fraction(wage[captain], quality[captain])
#             prices = []
#             for worker in range(N):
#                 price = factor * quality[worker]
#                 if price >= wage[worker]:
#                     prices.append(price)
                
#             if len(prices) >= K: 
#                 prices.sort()
#                 ans = min(ans, sum(prices[:K]))

#         return float(ans)
    
    
    
    
    
    


class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        from fractions import Fraction
        
        # sorting workers based on the ration of wage and quality
        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) # max heap based off quality
            heapSum += q
            
            if len(heap) > K:# if len of heap > K add largest heap elem
                heapSum += heapq.heappop(heap)
            
            if len(heap) == K:
                ans = min(ans, ration * heapSum)
        
        return float(ans)