题目描述

查理获得了一家运输公司的定期航线。为了赢利，他必须尽可能地降低成本。他的公司有 $N$ ($N$ 是偶数)个飞行员组成 $N/2$ 个机组，每个机组包括两个飞行员——机长和他的助手，机长必须比他的助手年长。每个飞行员有两个可能的工资合同——作为机长或作为助手。同一个飞行员当机长的工资要高于当助手的工资，然而就同一个机组而言，一个助手的工资可能高于他的机长。

编程帮助查理计算将飞行员按最佳组合编组后，所需支付给飞行员的最少工资总额。

输入格式

第 1 行 1 个偶数 $N$, $2≤N≤10000$, 表示查理公司所用的飞行员数量。 接下来的 $N$ 行，包含每个飞行员的工资，按飞行员的年龄排序，最年轻的飞行员的工资排在第一个。每行包含两个整数 $N$ 和 $Y$, 由一个空格隔开, $1≤Y<X≤00000$, $X$表示该飞行员当机长的工资, $Y$ 表示当助手的工资。

输出格式

一行一个数，表示查理所需支付给飞行员的最少工资总额。

样例

输入#1

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

输出#1

33000

数据范围/约定

时间空间限制：1s, 256MB.

题目来源

课课通 P399-3