Assign 2n Workers to Two Tasks to Minimize Total Time

You manage 2n workers and two tasks, A and B. Every worker must be assigned to exactly one task, and each task must be staffed by exactly n workers.

Workers are not equally good at both tasks. Worker i needs time[i][0] hours to do their share if assigned to task A, and time[i][1] hours if assigned to task B.

Return the minimum possible total number of hours worked, summed over all 2n workers, over all valid assignments.

Examples

Example 1

Input: time = [[10, 20], [30, 200], [400, 50], [30, 20]]
Output: 110

Assign workers 0 and 1 to task A (10 + 30 hours) and workers 2 and 3 to task B (50 + 20 hours). Total = 110. No other assignment with two workers per task does better.

Example 2

Input: time = [[5, 8], [2, 4]]
Output: 9

With n = 1, one worker goes to each task. Assigning worker 0 to task B and worker 1 to task A costs 8 + 2 = 10; assigning worker 0 to task A and worker 1 to task B costs 5 + 4 = 9. The minimum is 9.

Example 3

Input: time = [[7, 7], [3, 3], [1, 9], [9, 1]]
Output: 12

Workers 2 and either of {0, 1} go to task A, and worker 3 with the remaining one goes to task B: 1 + 3 + 1 + 7 = 12.

Constraints

• time.length == 2n where 1 <= n <= 10^5
• 1 <= time[i][0], time[i][1] <= 10^9
• The answer fits in a signed 64-bit integer.
• An O(n log n) solution is expected; trying all assignments is far too slow.

Output

Return the minimum total hours as an integer.