OJ现已增加邮箱找回密码功能,还没有绑定邮箱的同学们请抓紧时间,以免密码丢失无法找回


问题1292--二元组分配

1292: 二元组分配

时间限制: 1 Sec  内存限制: 128 MB
提交: 131  解决: 56
[提交] [状态] [讨论版] [命题人:]

题目描述

给你n个二元组(x,y),并且最开始有两个空集合A,B
对于每个二元组你需要抉择如何将x,y分配给A,B,
使得每次分配A,B都能得到一个元素,现在需要你求解分配完之后
最小化max(A)+max(B)的答案  (其中max(A)意思为A集合中的最大值)

输入

先输入一个n,接下来n个二元组(ai,bi)   其中(1<=n<=200000  , 1<=ai,bi<=1000000 )

输出

输出一个整数,即最小化max(A)+max(B)后的答案

样例输入 Copy

6
1 4
1 8
2 3
2 7
3 1
4 2

样例输出 Copy

10

提示

样例解释:
分配如下
A        B
8        1
4        1
3        1
7        2
3        1
4        2
答案为:8+2=10

来源/分类