Faster but longer solution
\n# Complexity\n- Time complexity: O(n\log(n)) due to sorting and the heap.\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(n) \n Add your 
\n# Complexity\n- Time complexity: $$O(n\\log(n))$$ due to sorting and the heap.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$ \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n\n    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n\n        cats = defaultdict(list)\n        for profit, cat in items:\n            cats[cat].append(profit)\n        for cat in cats:\n            cats[cat].sort()\n        \n        sorted_cats = sorted(cats, key=lambda x: -cats[x][-1])\n        # print(f"{sorted_cats=}")\n\n        base_total = 0\n        heap = []\n        max_profit = 0\n        total_profit = 0\n        for i, cat in enumerate(sorted_cats):\n            stack = cats[cat]\n            profit = stack.pop()+2*i+1\n            # print(f"{i=}, {cat=}, {stack=}, {profit=}")\n            if i+len(heap) < k:\n                total_profit += profit\n            elif heap:\n                total_profit -= heapq.heappop(heap)\n                total_profit += profit\n            else:\n                break\n\n            while stack:\n                profit = stack.pop()\n                if i + 1 + len(heap) < k:\n                    total_profit += profit\n                    heapq.heappush(heap, profit)\n                elif heap and profit > heap[0]:\n                    total_profit += profit-heap[0]\n                    heapq.heapreplace(heap, profit)\n                else:\n                    break\n\n            if total_profit > max_profit:\n                max_profit = total_profit\n            # print(f"{i=}, {base_total=} {cat=} {heap=}")\n        \n        return max_profit\n\n\n```
['Heap (Priority Queue)', 'Python3']