beats 100%, nlogn sort with explanation
Approach\n Describe your approach to solving the problem. \n1) add highest profits with a unique category to a min heap.\n2) if heap is less than k add highest 
# Approach\n<!-- Describe your approach to solving the problem. -->\n1) add highest profits with a unique category to a min heap.\n2) if heap is less than k add highest profits that are not unique\n3) loop through remaining values, if any has a profit greater than 2 * (number of unique categories in heap) - 1 + min_profit in heap, replace that profit with looped value and reduce unique categories by one\n4)sum values in heap and mult by square of unique categories\n\nProof it works:\nthe looped values either have a duplicate category or is unique. If it has a unique category, because we placed unique categories with max profit in the heap first these values can be ignored since they are unique items with lowers profits that were not added to the heap therefore the only looped values that matter are high profits with a duplicate category.\nThe min profit in the heap can either have a unique category or is duplicate. If its category is duplicate it means we have added all unique categories of highest profits and ran out of unique values therefor we added duplicate values with highest profits therefore every other value is duplicate with less profit therefore can be skipped. If the min_heap profit is a unique category than the value it adds to the sum is min_profit + (unique_cats)^2 and the profit the looped value with dup category adds is competitor_profit + (unique_cats - 1) ^ 2 =>\ncompetitor_profit + unique_cats^2 - 2 * unique_cats + 1\ntherefore competitor profit must defeat the min_profit + 2 * unique_cats - 1. you must decrement the unique_cats if min_profit was deleted for the next iteration since that cat will be lost in the next calculation\n# Complexity\n- Time complexity: O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n# Code\n```\nclass Solution {\n    public long findMaximumElegance(int[][] items, int k) {\n        Deque<Integer> pq = new ArrayDeque<>();\n        Arrays.sort(items, (a, b) -> b[0] - a[0]);\n        Set<Integer> uniq = new HashSet<>();\n        int n = items.length;\n        for (int i = 0; i < n && pq.size() < k; i++) {\n            int cat = items[i][1];\n            if (!uniq.contains(cat)) {\n                pq.addLast(items[i][0]);\n                items[i][0] = -1;\n                uniq.add(cat);\n            }\n        }\n        int size = uniq.size();\n        long res = 0;\n        boolean flag = pq.size() < k;\n        for (int i = 0; i < n; i++) {\n            if (items[i][0] < 0) continue;\n            if (pq.size() < k && flag) {\n                pq.addFirst(items[i][0]);\n                flag = pq.size() < k;\n                continue;\n            }\n            int min_profit = pq.pollLast();\n            int competitor = items[i][0];\n            if (competitor > (long)min_profit + 2 * (long)size - 1) {\n                res += competitor;\n                size--;\n            }\n            else {\n                res += min_profit;\n                break;\n            }\n        }\n        while(pq.size() > 0) res += pq.poll();\n        res += (long) size * (long) size;\n        return res;\n    }\n}\n```
['Java']