Greedy Approach
We want to calculate : total_profit + distinct_categories^2\n\n We sort profit in descending order and take first k  profits including duplicate categories\n Wh
We want to calculate : **total_profit + distinct_categories^2**\n\n* We sort profit in descending order and take first k  profits including duplicate categories\n* When we reach first k items , now we can maximazie distinct_categories by adding them into set and removing lowest duplicate items from set\n\n```\n\n#define ll long long\nclass Solution\n{\n    public:\n    \n        ll max(ll a,ll b)\n        {\n            return (a>b)?a:b;\n        }\n        long long findMaximumElegance(vector<vector < int>> &items, int k)\n        {\n\n            sort(items.begin(), items.end(), [& ](const vector<int> &a, const vector<int> &b)\n            {\n                return a[0] > b[0];\n\t});\n\n            ll res = 0, currSum = 0;\n\n            vector<int> duplicate;\n            unordered_set<int> seen;\n\n            for (int i = 0; i < items.size(); i++)\n            {\n                if (i < k)\n                {\n                    if (seen.count(items[i][1]))\n                    {\n                        duplicate.push_back(items[i][0]);\n                    }\n                    currSum += items[i][0];\n                }\n                else if (seen.find(items[i][1]) == seen.end())\n                {\n                    if (duplicate.empty())\n                        break;\n\n                    currSum += items[i][0] - duplicate.back();\n                    duplicate.pop_back();\n                }\n                seen.insert(items[i][1]);\n\n                res = max(res, currSum + 1ll *seen.size()*seen.size());\n            }\n            return res;\n        }\n};\n```
['Greedy', 'C']