猪展比赛
题目描述
佩奇农场养了N个品种的猪，为了让自己的农场更加有名，他决定带小猪们参加一场重要的猪展比赛，佩奇为每个品种选择了若干头重量相同的猪参加比赛，所有品种的猪一共有M头。
猪展评委们发现，每只猪在与其他猪一起比赛时会更加自信，因此决定将M头猪（M为偶数）分成M/2对进行比赛。每一对（两只）猪都将被送到一个独立的展位中进行比赛，所有的猪配对结束后，将同时开赛。
在比赛中，由于每一对猪的重量差异，导致比赛时间也有差异。如果两只猪的重量分别为Ai和Bi，则这对猪一起比赛需要Ai + Bi的时间。
请帮助佩奇农场的农场主以最佳方式将猪配对，使得所有的猪同时开赛之后，以最短的时间结束比赛。你只需要输出最短的比赛时间。
输入格式
第一行包含整数N，表示小猪的品种数量。（1≤N≤105）
接下来的N行，每行包含两个整数Xi和Yi，表示第i个品种的猪有Xi只，它们的重量均为Yi。（1≤Yi≤109）
∑Xi=M，也就是所有品种猪的总数为M只，M≤109，且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 长。