最短答疑总时间

题目描述

童程童美学院组织了一次编程竞赛，要学生两两组队进行比赛，两名学生可以共同进行赛前准备。竞赛组织者大白老师需要把n名参赛学生分成n/2队。在比赛之前，学校派出n/2名老师在同一时间开始给n/2队学生进行答疑。每名学生准备的问题数量不同，如果问题量为A个和B个的两名同学组队，那么老师将会需要A+B个单位时间来进行答疑。请帮忙计算出完成整个答疑过程所需的最短时间，假设大白老师以最佳方式将学生进行了组队。

输入格式

第一行包含一个整数m; （1≤m≤10^5^） 接下来m行，每行包含两个整数a和b，表示有a名学生，每人的问题量为b道。 （1≤b≤10^9^） （上述m行，所有a的总和为n，即学生的总数，1≤n≤10^9^）

输出格式

输出以最佳方式将学生组队的情况下，完成整个答疑所需的最短时间。

3
1 8
2 5
1 2

10

提示

（暂无提示）

来源

童程童美