C++ solution | Priority queues | sorting
\nclass Solution {\npublic:\n    unordered_set<int> on;\n    unordered_map<int,vector<int>> v;\n    unordered_map<int,int> mp;\n    priority_queue<array<int,2>>
```\nclass Solution {\npublic:\n    unordered_set<int> on;\n    unordered_map<int,vector<int>> v;\n    unordered_map<int,int> mp;\n    priority_queue<array<int,2>> hq;\n    long long findMaximumElegance(vector<vector<int>>& items, int k) {\n        for(int i=0; i<items.size(); i++) {\n            v[items[i][1]].push_back(items[i][0]);\n        }\n        for(pair<int,vector<int>> p : v) sort(v[p.first].rbegin(),v[p.first].rend());\n        \n        priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> pq;\n        \n        long long cnt = 0;\n        \n        for(pair<int,vector<int>> p : v) {\n             int d = p.first;\n             if(pq.size() < k) {\n                cnt+=v[d][0];\n                on.insert(d);\n                pq.push({v[d][0],d});\n             }else if(pq.top()[0] < v[d][0]) {\n                 on.erase(on.find(pq.top()[1]));\n                 on.insert(d);\n                 cnt-=pq.top()[0];\n                 pq.pop();\n                 cnt+=v[d][0];\n                 pq.push({v[d][0],d});\n             }\n           \n        }\n        \n        for(int pos : on) {\n            for(int i = 1; i < v[pos].size(); i++) hq.push({v[pos][i],pos});\n            mp[pos]++;\n        }\n        \n        cnt+=((long long) on.size() * on.size()); // one of the possible answer\n        \n        // we can do better by having a trade off by taking profit , removing category (descreasing distinct count)\n       \n        long long ans = cnt , len = mp.size();\n        while(hq.size()>0) {\n            int n = mp.size();\n            int highestValue = hq.top()[0] , highestArrayPos = hq.top()[1] , lowestValue = pq.top()[0] , lowestArrayPos = pq.top()[1];\n            if(len < k) {\n                mp[highestArrayPos]++;\n                cnt+=highestValue;\n                hq.pop();\n                ans = max(ans,cnt);\n                len++;\n            }else {\n                mp[lowestArrayPos]--;\n                mp[highestArrayPos]++;\n                if(mp[lowestArrayPos] == 0) mp.erase(lowestArrayPos);\n                cnt = cnt - ((long long)n * n) + ((long long)mp.size() * mp.size()) + highestValue - lowestValue;\n                hq.pop();\n                pq.pop();\n                ans = max(ans,cnt);\n            }\n        }\n        return ans;\n    }\n};\n```
['C', 'Sorting']