佩奇农场养了 N 个品种的猪，为了让自己的农场更加有名，他决定带小猪们参加一场重要的猪展比赛，佩奇为每个品种选择了若干头重量相同的猪参加比赛，所有品种的猪一共有 M 头。
猪展评委们发现，每只猪在与其他猪一起比赛时会更加自信，因此决定将 M 头猪（M为偶数）分成 M/2 对进行比赛。每一对（两只）猪都将被送到一个独立的展位中进行比赛，所有的猪配对结束后，将同时开赛。
在比赛中，由于每一对猪的重量差异，导致比赛时间也有差异。如果两只猪的重量分别为 A_i 和 B_i，则这对猪一起比赛需要 A_i + B_i 的时间。
请帮助佩奇农场的农场主以最佳方式将猪配对，使得所有的猪同时开赛之后，以最短的时间结束比赛。你只需要输出最短的比赛时间。
第一行包含整数 N，表示小猪的品种数量。（1 \le N \le 10^5）
接下来的 N 行，每行包含两个整数 X_i 和 Y_i ，表示第 i 个品种的猪有 X_i 只，它们的重量均为 Y_i。（1≤Y_i≤10^9）
\sum X_i = M，也就是所有品种猪的总数为 M 只，M≤10^9，且 M 为偶数。
输出比赛最少需要的时间。
3 1 8 2 5 1 2
10
5 2 9 1 8 10 20 3 6 4 10
30
【样例 1 解释】
将重量为 8 和 2 的猪配对，这对猪比赛需要的时间为 10。
将重量为 5 和 5 的猪配对，这对猪比赛需要的时间为 10。
则两个展位的比赛需要的总时间都为 10 ，因此这是最短的时间。如果进行其他配对，则有至少一个展位需要的时间比 10 长。
东方博宜OJ