O(n) single pass for adding items and a single pass for removing items
\nYou first greedily take all top profit values and get the minimal reasonable numCathegories. Then you increase the number of cathegories while removing the wo
\nYou first greedily take all top profit values and get the minimal reasonable numCathegories. Then you increase the number of cathegories while removing the worst (lowest) profits.\n\nOnly one structure `cat2count`: number of elements of a given cathegory in the current set.\n\n# Code\n```\ndef findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n    items.sort(key = lambda x: -x[0])\n    cat2count = defaultdict(lambda: 0)\n    nCat = 0\n    i = 0\n    sumProfit = 0\n    while k:\n        k -= 1\n        prof, cat = items[i]\n        if cat not in cat2count:\n            nCat += 1\n        cat2count[cat] += 1\n        sumProfit += prof\n        i += 1\n    ret = sumProfit + nCat**2\n    j = i\n    while j<len(items):\n        prof, cat = items[j]\n        if cat2count[cat] == 0:\n            sumProfit += prof\n            nCat += 1\n            cat2count[cat] = 1\n            while i>0:\n                i -= 1\n                if cat2count[items[i][1]] >= 2:\n                    sumProfit -= items[i][0]\n                    cat2count[items[i][1]] -= 1\n                    break\n            if i == 0:\n                return ret\n        j += 1\n        ret = max(ret, sumProfit + nCat**2)\n    return ret\n```
['Python3']