Simple Solution using PriorityQueue
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public long findMaximumElegance(int[][] items, int k) {\n        int n = items.length;\n        \n        TreeMap<Integer, List<Integer>> tm = new TreeMap();\n        \n        // tm(key, value) -- key = cat, value = list of profits\n        for(int i = 0; i < n; i++) {\n            if(!tm.containsKey(items[i][1]))\n                tm.put(items[i][1], new ArrayList());\n            tm.get(items[i][1]).add(items[i][0]);\n        }\n        \n        // Sort profits in desc order\n        for(Integer key : tm.keySet()) \n            Collections.sort(tm.get(key), (a, b) -> b - a);\n        \n        // System.out.println(tm);\n        \n        HashMap<Integer, Integer> hm = new HashMap();\n        PriorityQueue<int[]> minHp = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);\n        PriorityQueue<int[]> maxHp = new PriorityQueue<int[]>((a, b) -> b[0] - a[0]);\n        \n        // put max profit of each category in max heap\n        for(Map.Entry<Integer, List<Integer>> map : tm.entrySet()) {\n            maxHp.add(new int[] {map.getValue().get(0), map.getKey(), 0});\n        }\n        \n        int cnt = k;\n        long sum = 0, sqr = 0, maxEleg = 0;\n        List<int[]> list = new ArrayList();\n        \n        // Get k max profit from all distinct category\n        while(cnt-- > 0) {\n            int[] top = maxHp.poll();\n            sum += top[0];\n            hm.put(top[1], hm.getOrDefault(top[1], 0) + 1);\n            minHp.add(new int[] {top[0], top[1], top[2]});\n            \n            if(top[2] + 1 < tm.get(top[1]).size()) {\n                top[2]++;\n                top[0] = tm.get(top[1]).get(top[2]);\n                //maxHp.add(top);\n                if(list != null)\n                    list.add(top);\n                else\n                    maxHp.add(top);\n            }\n            \n            if(maxHp.isEmpty() && list != null) {\n                for(int[] a : list)\n                    maxHp.add(a);\n                list = null;\n            }\n        }\n        if(list != null) {\n        for(int[] a : list)\n                maxHp.add(a);\n        }\n        \n        // System.out.println(Arrays.toString(maxHp.peek())+" "+sum+" "+hm);\n        sqr = (long)Math.pow(hm.size(), 2);\n        maxEleg = sum + sqr;\n        \n        while(!maxHp.isEmpty()) {\n            int[] next = maxHp.poll();\n            int[] top = minHp.poll();\n            \n            sum -= top[0];\n            sum += next[0];\n            \n            remove(hm, top[1]);\n            hm.put(next[1], hm.getOrDefault(next[1], 0) + 1);\n            \n            sqr = (long)Math.pow(hm.size(), 2);\n            maxEleg = Math.max(maxEleg, sum + sqr);\n            \n            minHp.add(new int[] {next[0], next[1], next[2]});\n            if(next[2] + 1 < tm.get(next[1]).size()) {\n                next[2]++;\n                next[0] = tm.get(next[1]).get(next[2]);\n                maxHp.add(next);\n            }\n        }\n        \n        return maxEleg;\n    }\n    \n    public void remove(HashMap<Integer, Integer> hm, int x) {\n        if(hm.get(x) == 1)\n            hm.remove(x);\n        else\n            hm.put(x, hm.get(x) - 1);\n    }\n}\n\n\n\n\n\n\n\n\n\n\n\n\n```
['Java']