Greedy Python + detailed comments
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst, compute the elegance of the subseq of k items with maximum total profit. \nThen 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst, compute the elegance of the subseq of k items with maximum total profit. \nThen we iterate by adding items of the highest profit from new categories while removing items of the lowest profit from duplicate categories. \nIn this process we will compute the maximum elegance of k items for every possible number of categories used. \nThe final answer is the maximum of all these values.\n\n# Code\n```\nclass Solution:\n    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n        n = len(items)\n        # sort items in descending order of profit\n        items.sort(key = lambda item: -item[0])\n        # stack of items that can be replaced by an item from a new category\n        dupes = []\n        # set of categories included in our subseq of k items\n        seen = set()\n\n        # calculate the elegance of the k items with maximum total profit\n        total_profit = 0\n        for i in range(k):\n            profit, category = items[i]\n            total_profit += profit\n            # check if item is from a new category; if not, we add it to dupes\n            if category not in seen:\n                seen.add(category)\n            else:\n                dupes.append(profit)\n        maxElegance = total_profit + len(seen)**2\n        \n        # while our subseq of k items contains less than k categories\n        #   pop the lowest profit item of category with multiple items\n        #   add the highest profit item of a new category\n        for i in range(k, n):\n            if len(seen) == k:\n                break\n            profit, category = items[i]\n            if category not in seen:\n                total_profit -= dupes.pop()\n                total_profit += profit\n                seen.add(category)\n                maxElegance = max(maxElegance, total_profit + len(seen)**2)\n\n        return maxElegance\n```
['Greedy', 'Python', 'Python3']