# Given calls to insert items with scores, keep track of the k best

class KBest:
    def __init__(self, k):
        self.k = k
        self.bestItems = []

    # Keep bestItems sorted so the worst one is last
    def insert(self, item, score):
        def lowerScore(x, y):
            return -cmp(x[0],y[0])
        
        if len(self.bestItems) < self.k:
            self.bestItems.append((score, item))
            self.bestItems.sort(lowerScore)
        elif score > self.bestItems[-1][0]:
            self.bestItems.pop()
            self.bestItems.append((score, item))
            self.bestItems.sort(lowerScore)

    def kBest(self):
        return self.bestItems

    def best(self):
        return self.bestItems[0]

    
        
