Stack + Sorting
\nclass Solution:\n    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n        n = len(items)\n        items.sort(reverse=True)\n        
```\nclass Solution:\n    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n        n = len(items)\n        items.sort(reverse=True)\n        seen_category = set()\n        stk = []\n        ans = 0\n        for i in range(k):\n            profit, cat = items[i]\n            ans += profit\n            if cat in seen_category:\n                stk.append(profit)\n            else:\n                seen_category.add(cat)    \n        i = k\n        cur = ans\n        for sq in range(1, k + 1):\n            if len(seen_category) < sq:\n                while i < n and items[i][1] in seen_category:\n                    i += 1   \n                if i == n or len(stk) == 0: break    \n                p = stk.pop()\n                cur = cur - p + items[i][0]\n                seen_category.add(items[i][1])\n            ans = max(ans, cur + sq * sq)\n        return ans\n```
['Python3']