java solution with time complexity:O(n.logn)      Space complexity:O(n)
class Solution {\n    public long findMaximumElegance(int[][] arr, int k) {\n        int n = arr.length;\n        long s = 0, ms = 0, distinct = 0;\n        int
class Solution {\n    public long findMaximumElegance(int[][] arr, int k) {\n        int n = arr.length;\n        long s = 0, ms = 0, distinct = 0;\n        int[] freq = new int[n + 1];\n        Arrays.sort(arr, (a, b) -> b[0] - a[0]);\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);\n        for (int i = 0; i < k; i++) {\n            s += arr[i][0];\n            if (freq[arr[i][1]] == 0)\n                distinct++;\n            if (freq[arr[i][1]] > 0)\n                pq.add(new int[] { arr[i][0], arr[i][1] });\n            freq[arr[i][1]]++;\n            ms = Math.max(s + distinct * distinct, ms);\n\n        }\n        for (int i = k; i < n; i++) {\n            if (freq[arr[i][1]] == 0) {\n                if (!pq.isEmpty()) {\n                    s -= pq.poll()[0];\n                    s += arr[i][0];\n                    distinct++;\n                    freq[arr[i][1]]--;\n                    ms = Math.max(s + (distinct) * (distinct), ms);\n                }\n            }\n        }\n        return ms;\n    }\n}
[]