Probably the easiest solution.
Intuition\nThere is an inclination to go towards DP when you hear subsequences. The constraints made me feel it was greedy.\n\n# Approach\nFirst sort the array 
# Intuition\nThere is an inclination to go towards DP when you hear subsequences. The constraints made me feel it was greedy.\n\n# Approach\nFirst sort the array by profits in descending order.\nSimply take first k elements. Since there is a factor of categories in profit calculation, keep a set with all categories. In case you have a repeated category, push into a vector/stack which stores the values. Next is simple, whichever repeated category has the least profit value is to be replaced by an element whose category hasn\'t been encountered yet.\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    long long findMaximumElegance(vector<vector<int>>& items, int k) \n    {\n        sort(items.rbegin(), items.rend());\n        stack<int> minAtTop;\n        unordered_set<int> s;\n        long long sum = 0;\n        for(int i=0;i<k;i++)\n        {\n            sum += items[i][0];\n            if(s.count(items[i][1])) minAtTop.push(items[i][0]);\n            else s.insert(items[i][1]);\n        }\n        long long ans = sum + s.size()*1LL*s.size();\n        for(int i=k;i<items.size();i++)\n        {\n            if(!s.count(items[i][1]) && !minAtTop.empty())\n            {\n                s.insert(items[i][1]);\n                sum -= minAtTop.top();\n                minAtTop.pop();\n                sum += items[i][0];\n                int n = s.size();\n                ans = max(ans, sum + n*1LL*n);\n            }\n        }\n        return ans;\n    }\n};\n```
['Greedy', 'Sorting', 'C++']