猪展比赛

题目描述

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

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

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

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

输入

第一行包含整数 $N$ ，表示小猪的品种数量。（$1≤N≤10^{5}$）

接下来的 $N$ 行，每行包含两个整数 $X_{i}$ 和 $Y_{i}$ ，表示第 $i$ 个品种的猪有 $X_{i}$ 只，它们的重量均为 $Y_{i}$。（$1≤Y_{i}≤10^{9}$）

$∑X_{i}=M$，也就是所有品种猪的总数为 $M$ 只，$M≤10^{9}$，且 $M$ 为偶数。

输出

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

样例

输入数据1

3
1 8
2 5
1 2

输出数据1

10

输入数据2

5
2 9
1 8
10 20
3 6
4 10

输出数据2

30

说明

【样例 $1$ 解释】

将重量为 $8$ 和 $2$ 的猪配对，这对猪比赛需要的时间为 $10$ 。

将重量为 $5$ 和 $5$ 的猪配对，这对猪比赛需要的时间为 $10$。

则两个展位的比赛需要的总时间都为 $10$ ，因此这是最短的时间。如果进行其他配对，则有至少一个展位需要的时间比 $10$ 长。