Adoption

This problem originally appeared in the 2021 final exam.

Time Limit: 1 second

Calum is the manager of an animal shelter, where he has n cats and n dogs. After much advertising, he has successfully identified 2n people who each want exactly one pet, and he wants to give out the cats and dogs to satisfy them as best he can.

Calum knows how much happiness each person would get from adopting a cat, and also how much they would get from adopting a dog. Help Calum distribute the animals so as to maximise the total happiness of the pet owners.

Input

The first line of input consists of an integer n, representing the number of cats (and also the number of dogs). 2n lines follow, the ith consisting of two space-separated integers, c_i and d_i ( − 100, 000 ≤ c_i, d_i ≤ 100, 000), representing the happiness the ith person would get from a cat and from a dog respectively.

Output

Output a single integer, the maximum total happiness that can be achieved.

Subtasks

30 points: 1 ≤ n ≤ 5, 000.

70 points: 1 ≤ n ≤ 100, 000.

Sample Input 1

2
1 2
2 1
0 3
2 -1

Sample Output 1

9

Sample Input 2

2
1 2
2 1
0 3
2 5

Sample Output 2

11

Sample Input 3

2
1 2
2 1
0 3
-1 -2

Sample Output 3

6

Explanation

In sample case 1, it is optimal to give cats to the second and fourth people, and dogs to the first and third, for total happiness 2 + 2 + 3 + 2 = 9.

In sample case 2, it is optimal to give cats to the first two people, and dogs to the last two, for total happiness 1 + 2 + 3 + 5 = 11. Note that three of the four people prefer dogs, but there are only two dogs available.

In sample case 3, it is again optimal to give cats to the second and fourth people, and dogs to the first and third, for total happiness 2 + 2 + 3 + ( − 1) = 6. Note that it is possible for a person to have negative happiness for both cats and dogs, but they receive a pet anyway.