A company flies 2N candidates to interviews, splitting them so that exactly N go to city A and exactly N go to city B. Candidate i costs a[i] to fly to city A and b[i] to fly to city B.
Return the minimum possible total flight cost over all valid splits.
Input format
Line 1: an integer N (there are 2N candidates).
Next 2N lines: two integers a[i] and b[i] for one candidate — the cost to city A and to city B.
Output format
A single integer: the minimum total cost with exactly N candidates sent to each city.
Constraints
- 1 <= N <= 50000
- 0 <= a[i], b[i] <= 1000000