题目：猪展比赛

题目描述

佩奇农场养了 $N$ 个品种的猪，为了让自己的农场更加有名，他决定带小猪们参加一场重要的猪展比赛，佩奇为每个品种选择了若干头重量相同的猪参加比赛，所有品种的猪一共有 $M$ 头。

猪展评委们发现，每只猪在与其他猪一起比赛时会更加自信，因此决定将 $M$ 头猪（$M$ 为偶数）分成 $M/2$ 对进行比赛。每一对（两只）猪都将被送到一个独立的展位中进行比赛，所有的猪配对结束后，将同时开赛。

在比赛中，由于每一对猪的重量差异，导致比赛时间也有差异。如果两只猪的重量分别为 $A_i$ 和 $B_i$，则这对猪一起比赛需要 $A_i + B_i$ 的时间。

请帮助佩奇农场的农场主以最佳方式将猪配对，使得所有的猪同时开赛之后，以最短的时间结束比赛。你只需要输出最短的比赛时间。

输入格式

第一行包含整数 $N$，表示小猪的品种数量。（$1 \leq N \leq 10^5$）
接下来的 $N$ 行，每行包含两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 个品种的猪有 $X_i$ 只，它们的重量均为 $Y_i$。（$1 \leq Y_i \leq 10^9$）
$\sum X_i = M$，也就是所有品种猪的总数为 $M$ 只，$M \leq 10^9$，且 $M$ 为偶数。

输出格式

输出比赛最少需要的时间。

样例

样例 1

• 输入

3  
1 8  
2 5  
1 2  

• 输出

10  

样例 2

• 输入

5  
2 9  
1 8  
10 20  
3 6  
4 10  

• 输出

30  

说明

【样例 1 解释】
将重量为 8 和 2 的猪配对，这对猪比赛需要的时间为 10。
将重量为 5 和 5 的猪配对，这对猪比赛需要的时间为 10。
则两个展位的比赛需要的总时间都为 10，因此这是最短的时间。如果进行其他配对，则有至少一个展位需要的时间比 10 长。