[Lydsy2017年5月月赛]叠塔游戏

时间限制:20s      空间限制:256MB

题目描述

小Q正在玩一个叠塔的游戏,游戏的目标是叠出尽可能高的塔。在游戏中,一共有n张矩形卡片,其中第i张卡片的
长度为a_i,宽度为b_i。小Q需要把所有卡片按一定顺序叠成一座塔,要求对于任意一个矩形,它的长度要严格大
于它上边的任意一个矩形的长度。塔的高度为所有矩形的宽度之和。在游戏中,小Q可以将卡片翻转90度来使用,
而且必须用上全部n张卡片。请写一个程序,帮助计算小Q能叠出最高的塔的高度。


输入格式

第一行包含一个正整数n(1<=n<=250000),即卡片的个数。
接下来n行,每行两个正整数a_i,b_i(1<=a_i,b_i<=10^9),分别表示每张卡片的长度和宽度。


输出格式

输出一行一个整数,即最高的塔的高度,输入数据保证一定存在解。


样例输入

3
5 16
10 5
5 10

样例输出

20

提示

没有写明提示


题目来源

鸣谢Claris上传试题

Menuappsclose