题目描述

ls的公司预聘用$N$（为偶数）名飞行员组成$N \over 2$个机组，每个机组配备两个飞行员，一名机长和一名助手，机长必须比他的助手年长。

每个飞行员有两个可能的工资合同：作为机长和作为助手。同一个飞行员当机长的工资要高于当助手的工资，而在同一个机组，助手的工资可能是高于机长的工资。

对每个飞行员签订的合同，如何组合让ls付出的工资最少？

输入格式

第一行包含一个正整数n，接下来的n行，每行包含两个数，分别表示一名飞行员作为机长和作为助手的合同工资。

数据按照飞行员的年龄从小到大给出。

输出格式

一个数，表示要支付的最少工资。

样例

输入

6
5000 3000
4000 1000
9000 7000
11000 5000
7000 3000
8000 6000

输出

33000

提示

数据范围：$2 \le N \le 10000$，工资为不会超过100 000的正整数。