1class Solution {
2    public long maxSum(int[] nums, int[] threshold) {
3        int n = nums.length;
4
5        // Create an index array to sort element indices by their threshold values
6        Integer[] indices = new Integer[n];
7        Arrays.setAll(indices, i -> i);
8
9        // Sort indices in ascending order based on the corresponding threshold value
10        Arrays.sort(indices, Comparator.comparingInt(i -> threshold[i]));
11
12        // TreeMap acts as a multiset: key = element value, value = count of that element
13        // It keeps elements sorted so we can quickly access the largest available value
14        TreeMap<Integer, Integer> availableValues = new TreeMap<>();
15
16        long answer = 0;
17
18        // Iterate step by step; at each step we "unlock" elements whose threshold is reached,
19        // then greedily pick the largest available value
20        for (int i = 0, step = 1; ; ++step) {
21            // Add all elements whose threshold is satisfied at the current step
22            while (i < n && threshold[indices[i]] <= step) {
23                availableValues.merge(nums[indices[i]], 1, Integer::sum);
24                ++i;
25            }
26
27            // If no elements are available, we are done
28            if (availableValues.isEmpty()) {
29                break;
30            }
31
32            // Greedily take the largest available value to maximize the sum
33            int maxValue = availableValues.lastKey();
34            answer += maxValue;
35
36            // Decrement the count of the chosen value; remove it entirely if count drops to 0
37            if (availableValues.merge(maxValue, -1, Integer::sum) == 0) {
38                availableValues.remove(maxValue);
39            }
40        }
41
42        return answer;
43    }
44}
45

1class Solution {
2public:
3    long long maxSum(vector<int>& nums, vector<int>& threshold) {
4        int n = nums.size();
5
6        // Build an index array [0, 1, ..., n-1] so we can sort by threshold
7        // without disturbing the original nums/threshold arrays.
8        vector<int> order(n);
9        iota(order.begin(), order.end(), 0);
10
11        // Sort indices in ascending order of their threshold value.
12        // Elements with smaller thresholds become available earlier.
13        sort(order.begin(), order.end(),
14             [&](int lhs, int rhs) { return threshold[lhs] < threshold[rhs]; });
15
16        // multiset keeps all currently available values, ordered ascending,
17        // so the largest available value is always at the end.
18        multiset<int> available;
19        long long answer = 0;
20        int nextIdx = 0;  // pointer into the sorted "order" array
21
22        // Iterate step by step (step = 1, 2, 3, ...).
23        for (int step = 1;; ++step) {
24            // Release every element whose threshold has been reached at this step.
25            while (nextIdx < n && threshold[order[nextIdx]] <= step) {
26                available.insert(nums[order[nextIdx]]);
27                ++nextIdx;
28            }
29
30            // No element is available to pick: stop processing.
31            if (available.empty()) {
32                break;
33            }
34
35            // Greedily take the largest available value for this step.
36            auto largest = prev(available.end());
37            answer += *largest;
38            available.erase(largest);
39        }
40
41        return answer;
42    }
43};
44

1// Max-heap stored as a global array; the largest value sits at index 0.
2const heap: number[] = [];
3
4// Insert a value into the max-heap, restoring the heap property by sifting up.
5function heapPush(value: number): void {
6    heap.push(value);
7    let child = heap.length - 1;
8    while (child > 0) {
9        const parent = (child - 1) >> 1;
10        if (heap[parent] >= heap[child]) {
11            break;
12        }
13        [heap[parent], heap[child]] = [heap[child], heap[parent]];
14        child = parent;
15    }
16}
17
18// Remove and return the maximum value, restoring the heap property by sifting down.
19function heapPop(): number {
20    const top = heap[0];
21    const last = heap.pop()!;
22    if (heap.length > 0) {
23        heap[0] = last;
24        let parent = 0;
25        const size = heap.length;
26        while (true) {
27            const left = parent * 2 + 1;
28            const right = parent * 2 + 2;
29            let largest = parent;
30            if (left < size && heap[left] > heap[largest]) {
31                largest = left;
32            }
33            if (right < size && heap[right] > heap[largest]) {
34                largest = right;
35            }
36            if (largest === parent) {
37                break;
38            }
39            [heap[parent], heap[largest]] = [heap[largest], heap[parent]];
40            parent = largest;
41        }
42    }
43    return top;
44}
45
46function maxSum(nums: number[], threshold: number[]): number {
47    const length = nums.length;
48
49    // Reset the global heap so repeated calls start clean.
50    heap.length = 0;
51
52    // Build a list of indices sorted by their threshold value in ascending order.
53    const sortedIndices = Array.from({ length }, (_, i) => i).sort(
54        (a, b) => threshold[a] - threshold[b],
55    );
56
57    let answer = 0;
58
59    // pointer scans sortedIndices; step represents the current "time" level.
60    for (let pointer = 0, step = 1; ; ++step) {
61        // Enqueue every value whose threshold is now reachable at this step.
62        while (pointer < length && threshold[sortedIndices[pointer]] <= step) {
63            heapPush(nums[sortedIndices[pointer]]);
64            ++pointer;
65        }
66
67        // No eligible value remains, so we are finished.
68        if (heap.length === 0) {
69            break;
70        }
71
72        // Greedily take the largest currently available value.
73        answer += heapPop();
74    }
75
76    return answer;
77}
78