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