普及模拟赛 6 - B

题目背景

小D进入小学了，在小学他希望自己能够得到个人能力的提升，因此他要合理安排课程。

题目描述

小D进入小学之后，得到了一份新的课程表。

课程表每周共有 $2n$ 节课，可以分别分配给语文、数学（没有音体美好惨~），每一种科目安排在不同的时间所产生的贡献是不同的。

小D希望你能够帮助他合理安排自己的课程，使得他能够获得的提升值最高。

现在分别给定你语文、数学安排在每一节能够获得的提升值，你需要把其中的 $n$ 节分配给语文，另外 $n$ 节分配给数学。你需要求出在最优分配方案下能得到的最大的提升值总和。

输入格式

输入共 $2n + 1$ 行

第一行 $1$ 个整数 $n$ ，如题意所示。

接下来 $2n$ 行，每行 $2$ 个整数 $a_i,b_i$，分别表示第 $i$ 节选择语文、数学的提升值。

输出格式

输出 $1$ 行， $1$ 个整数，表示选择 $n$ 节语文和 $n$ 节数学的最大的提升值之和。

输入输出样例 #1

输入 #1

3
6 3
3 4
4 4
4 6
2 5
6 1

输出 #1

31

输入输出样例 #2

输入 #2

4
2 3
2 2
2 3
1 4
3 2
1 2
2 6
4 3

输出 #2

26

输入输出样例 #3,4

见下发文件。

说明/提示

对于前 $10\%$ 的数据，有 $2\le n \le10$ , $1\le a_i,b_i \le 5000$
对于前 $40\%$ 的数据，有 $2\le n \le2000$ , $1\le a_i,b_i \le 5000$
对于所有数据，有 $2\le n \le 5 \times 10^5$ ，$1\le a_i,b_i \le 10^9$