1884:学校分配

文件提交:无需freopen 内存限制:128 MB 时间限制:1.000 S
评测方式:普通裁判 命题人:
提交:4 解决:2

题目描述

蒜头君的学校在市区和郊区各有一座校区。当学期开学时,学校总共招收了 $2N$ 名学生,但每个校区最多只能容纳各 $N$ 名学生。也就是说,必须把这 $2N$ 名学生分配到市区及郊区各 $N$ 名。

作为学长,校长让蒜头君调查了新同学对于去往市区校区及郊区校区的意愿,我们用 $S_i$ 和 $J_i$ 来表示。$S_i$ 代表第 $i$ 名学生如果去往市区校区时,他的满意指数; $J_i$ 代表第 $i$ 名学生如果去往郊区校区时,他的满意指数。

校长想知道如何分配才能使这 $2N$ 名学生的满意指数之和最大?校长把这个艰巨的任务交给了蒜头君,你能帮忙蒜头君完成这个任务吗?

输入

第一行,包含一个整数 $N$

以下 $2N$ 行每行包含以空格分隔的两个整数 $S_i$ 和 $J_i$

$1\le N\le 1000; 0\le S_i,J_i \le 10^5$

输出

一个整数代表最高可能的满意指数之和。

样例输入-1 复制

2  
100 50  
80 80  
50 100  
10 30

样例输出-1 复制

310