I have a list of integer pairs. The value of this list is the sum of the maximum values of each pair.

For

(0, 5) (20, 5) (6, 8)

the value would be

5 + 20 + 8 = 33

Given a list like this, I need to maximize its value. The only operation I can do is swap an element of a pair with another element of a different pair.

For the example above I can do this

(6, 8) <> (0, 5)

The list would become

(0, 6) (20, 5) (5, 8) => value = 6 + 20 + 8 = 34

So in order to increase the value I'd need to find 2 pairs (a,b) (c,d) with min(a,b) > max(c,d) and then swap min(a,b) with max(c,d), right ? If no such pairs exist then the we cannot increase the value of the list.

Solution:
I need to keep the pairs sorted in descending order by the minimum value and in ascending order by the maximum value because I need to compare the pair with the greatest minimum to the one with smallest maximum.

I thought about using two heaps for this, a minheap which orders by maximums and a maxheap which orders by minimums. This way, each time I need to compare I can just compare the roots of the two heaps.

The problem is that I also need to update these values, by exchanging the minimum value of 1 pair with the maximum value of another pair and then reorder the heaps so I would need to also keep additional information for each heap node for the position in the other heap. Something like Dual heap in Double-ended priority queue.

Is this the best way to approach this problem, or are there better data structures that I can use?