Minimum Energy to Sort Objects by Volume

You are given n objects arranged in a row. Each object has a volume V and a mass M. The volumes are all distinct and are a permutation of the integers from \(1\) to \(n\), while the masses may not be unique.

Your task is to sort the objects in ascending order of their volumes using swaps. In each swap, you can exchange any two objects and the energy cost incurred is equal to the sum of their masses. Determine the minimum total energy required to sort the objects.

Note:

• The cost to swap two objects is: \(M_i + M_j\).
• You are allowed to swap any two objects regardless of their positions.
• If the objects are already sorted, the total energy cost is \(0\).

inputFormat

The first line contains an integer \(n\) (\(1 \leq n \leq 10^5\)), the number of objects. Each of the next \(n\) lines contains two integers \(V\) and \(M\) describing the volume and mass of an object. The volumes form a permutation of \(1\) through \(n\), and the masses are positive integers.

outputFormat

Output a single integer representing the minimum total energy required to sort the objects by volume in ascending order.

sample

3
2 4
3 2
1 3

11