Track Dups
We sort items by profit, and take first k items.\n\nWe also track how many unique categories cats are there. If we see another item in the existing category, we
We sort items by profit, and take first `k` items.\n\nWe also track how many unique categories `cats` are there. If we see another item in the existing category, we place it into `dups`.\n\nNow, let\'s see if we can improve our result by considering remaining `n - k` items:\n- If the item category already exists in `cats`, we ignore it. We already include items with larger profits from that category.\n- If the category does not exist, we take that item, and remove the smallest profit from `dups`.\n\nWe track and return the largest `res`.\n\n**C++**\n```cpp\nlong long findMaximumElegance(vector<vector<int>>& items, int k) {\n    sort(begin(items), end(items), greater<>());\n    vector<int> dups;\n    unordered_set<int> cats;\n    for (int i = 0; i < k; ++i)\n        if (!cats.insert(items[i][1]).second)\n            dups.push_back(items[i][0]);\n    long long sum = accumulate(begin(items), begin(items) + k, 0LL, [](long long s, const auto &i) {\n        return s + i[0];\n    });\n    long long res = sum + cats.size() * cats.size();\n    for (int i = k, j = dups.size() - 1; i < items.size() && j >= 0; ++i)\n        if (cats.insert(items[i][1]).second) {\n            sum = sum - dups[j--] + items[i][0];\n            res = max(res, sum + (long long)(cats.size() * cats.size()));\n        }\n    return res;\n}\n```
['C']