simple greedy with stack
Intuition\n\n\n# Approach\nget first k most profitable items, than try to increase numbers of unique catigories by dropping less profitable items.\n\n# Complexi
# Intuition\n\n\n# Approach\nget first k most profitable items, than try to increase numbers of unique catigories by dropping less profitable items.\n\n# Complexity\n- Time complexity:\n$$O(log(n)*n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    long long findMaximumElegance(vector<vector<int>>&X, int k) {\n        size_t best=0, current=0;\n        unordered_set<int>categories; stack<int>may_drop;\n        sort(X.begin(), X.end(), [](auto&l, auto&r){ return l[0] > r[0]; });\n        for(auto&x : X){\n            if (k) --k;\n            else if (may_drop.empty()) break;\n            else { current -= may_drop.top(); may_drop.pop(); }\n            current += x[0];\n            if (!categories.insert(x[1]).second) may_drop.push(x[0]);\n            best = max(best, current + categories.size() * categories.size());\n        }\n        return best;\n    }\n};\n```
['Greedy', 'C++']