Try all but update incrementally
Intuition\n- Sort items with deceasing profit, and choose the first k items.\n- This gives baseline answer ans, with # categories = c\n- Increase c step by step
# Intuition\n- Sort `items` with deceasing profit, and choose the first `k` items.\n- This gives baseline answer `ans`, with `# categories` = `c`\n- Increase `c` step by step up to `c = k`, while updating `ans` incrementally.\n- To do incremental update, replace the worst that is already in `ans` and **replaceable**, by next best in the sorted `items` array, using a min heap.\n \n\n# Code\n```\nclass Solution {\npublic:\n    long long findMaximumElegance(vector<vector<int>>& items, int k) {\n        int n = items.size();\n        sort(items.begin(), items.end(), [](auto const& a, auto const& b) { return a[0] > b[0]; });\n        long long ans = 0;\n        unordered_map<int, int> count;\n        struct ValId {\n            int val, id;\n            bool operator<(ValId const& that) const {\n                return val > that.val;\n            }\n        };\n        priority_queue<ValId> pq;\n        int i = 0;\n        for(; i < k; ++i) {\n            int val = items[i][0];\n            int id = items[i][1]-1;\n            ans += val;\n            count[id]++;\n            pq.emplace(val, id);\n        }\n        int sz = count.size();\n        long long sz2 = static_cast<long long>(sz) * sz;\n        ans += sz2;\n        //cout << ans << endl;\n        for(long long prev = ans; i < n && sz < k; ++i) {\n            //cout << "prev " << prev << \'\\t\';\n            long long cur = prev;\n            int val = items[i][0];\n            int id = items[i][1]-1;\n            //cout << "try " << i << " val " << val << " id " << id+1  << " sz " << sz << \'\\t\';\n            if(count.contains(id)) continue;\n            count[id]++;\n            cur -= sz2;\n            sz++;\n            sz2 = static_cast<long long>(sz) * sz;\n            cur += sz2 + val;\n            while(! pq.empty() ) {\n                auto [val, id] = pq.top();\n                //cout << "heap top " << val << ", " << id+1 << \'\\t\';\n                pq.pop();\n                if(count[id] > 1) {\n                    cur -= val;\n                    count[id]--;\n                    break;\n                }\n            }\n            //cout << "cur " << cur << endl;\n            if(cur > ans)\n                ans = cur;\n            prev = cur;\n        }\n        return ans;\n    }\n};\n```
['C++']