题目描述

Gooby 有 $N$ 个任务需要分配给同学们，恰好有 $2N$ 名同学，所以Gooby决定将他们两两组队，共组成 $N$ 队。

每队同学都会领到一个任务，并且每个同学都会有自己的能力值。假设能力值为 $A$ 和能力值为 $B$ 的同学组成了一队，那么他们完成分配到的任务的时间就是 $A+B$。

$N$ 队同学会同时开始做自己分配到的任务，要等所有队伍都完成任务，才算所有任务完成。Gooby 想要知道如何安排组队，才能够使得所有任务完成的最快，时间花费了多少。

输入格式

输入的第一行包含 $M$

接下来的 $M$ 行每行包含两个整数 $x$ 和 $y$，表示有 $x$ 名能力值为 $y$ 的同学。保证所有 $x$ 的总和为 $2N$。

输出格式

输出当按照最优组队方式时，完成所有任务所需要的最少时间。

输入输出样例 #1

输入 #1

3
1 8
2 5
1 2

输出 #1

10

样例1解释

组成两队：

• 8和2，花费时间为10
• 5和5，花费时间为10

因此一共需要花费10的时间，可以证明这是最优的答案。

输入输出样例 #2

样例2链接

说明/提示

对于50%的数据，保证所有的 $x = 1$

对于100%的数据，保证 $1 \le M \le 10^5, 2 \le 2N \le 10^9$ 且为偶数，且 $1 \le y \le 10^9$，保证所有的 $x$ 之和为 $2N$