💥💥 Beats 100% on runtime and memory [EXPLAINED]
IntuitionThe goal is to pick up to k items that maximize the sum of profits while ensuring we get the most distinct categories. If multiple items belong to the
# Intuition
The goal is to pick up to k items that maximize the sum of profits while ensuring we get the most distinct categories. If multiple items belong to the same category, only one of them can be included. To balance between maximizing the profit and respecting the category constraint, we must carefully manage how we add duplicate profits from the same category.

# Approach
I've started by sorting the items by profit in descending order, then loop through each item, adding its profit to a running total. We keep track of the categories we've seen using a HashSet<int>. If an item belongs to a category we’ve already seen, we add its profit to a list of duplicates (res). If we exceed the allowed number of items (k), we remove the smallest profit from res. When we have exactly k items, we calculate the current elegance, which is the sum of profits plus the square of the number of unique categories.

# Complexity
- Time complexity:
O(n log n) because we need to sort the items by profit. After sorting, we just loop through the items once, which is O(n).

- Space complexity:
O(n) because we use a HashSet<int> to track unique categories and a List<int> to store the duplicate profits for categories.

# Code
```csharp []
public class Solution
{
    public long FindMaximumElegance(int[][] items, int k)
    {
        // Sort items in descending order of profit
        Array.Sort(items, (a, b) => b[0].CompareTo(a[0]));

        // Initialize variables
        long runningVal = 0, maxVal = 0;
        HashSet<int> seen = new HashSet<int>();  // To track unique categories
        List<int> res = new List<int>();  // To hold profits of duplicate categories

        // Iterate through sorted items
        foreach (var item in items)
        {
            int profit = item[0];
            int category = item[1];

            // Add the current profit to running total
            runningVal += profit;

            // If category is unique, add it to seen set
            if (!seen.Contains(category))
            {
                seen.Add(category);
            }
            else
            {
                // Otherwise, add profit to res (duplicate category profits)
                res.Add(profit);
            }

            // Ensure we do not exceed k items
            while (res.Count > 0 && res.Count + seen.Count > k)
            {
                runningVal -= res[res.Count - 1];  // Remove the last duplicate profit
                res.RemoveAt(res.Count - 1);  // Pop from the list
            }

            // Update max elegance when we have exactly k items
            if (res.Count + seen.Count == k)
            {
                maxVal = Math.Max(maxVal, runningVal + (long)seen.Count * seen.Count);
            }
        }

        return maxVal;
    }
}

```
['Array', 'Hash Table', 'Dynamic Programming', 'Stack', 'Greedy', 'Breadth-First Search', 'Sorting', 'Heap (Priority Queue)', 'Quickselect', 'C#']