问题 3851 --配对

3851: 配对

题目描述

      John发现当有其他奶牛陪伴的时候,挤奶更容易。因此,他想把M(M<=1000000000,M是偶数)头奶牛配对成M/2对。这M/2对奶牛会被会被带到分开的谷仓同时挤奶。
    麻烦的是,每头奶牛都有不同的奶产量,如果两头配对好的奶牛的奶产量分别是A和B,那么一起要花费的时间是A+B。
    请帮助John确定花费总时间最少的方案。

输入

    第一行:整数N,1<=N<=100000。

    接下来N行,每行包含两个整数,xi,yi,表示有xi头奶牛的奶产量是yi。1<=yi<=1000000000。总奶牛数为M。

输出

   在最优方案下,挤完所有奶牛的时间。

样例输入输出

输入#1 复制
3
1 8
2 5
1 2
输出#1 复制
10

提示

序号 标题 作者 发表时间 费用 订购数 操作