小Y做比赛

发布时间: 2018年4月15日 22:51   最后更新: 2018年4月15日 23:25   时间限制: 1000ms   内存限制: 128M

埃森哲的员工可能会为我们的客户制定战略,开发或推荐信息技术,帮助他们最大程度实现数字化,或者,通过咨询团队提供上述服务的交付,以及处理客户的业务运营。当然,也少不了和同事们参加各种各样的比赛。

小Y正在和大家一起参加比赛,比赛共有$N$道题目,比赛规则是根据做出题目数量来确定排名的,当出题数相同则罚时少的排名在前,一位参赛选手罚时等于他每道做出的题目的罚时,做一道题目的罚时等于做出该题目时距离比赛开始后的时间,另外每次错误的提交也会增加罚时。

小Y 很厉害,他能做出所有的$N$道题目,并且不会有提交错误。而对于每道题目,他需要花费一定的读题时间和做题时间,当然他需要读过一道题才能去做那道题。小Y有一个做题习惯,就是仅当他有两道读过并且还没做出的题时,他才会去做题,并且会选择去做花费做题时间较少的那题。除了只剩一题的情况下,他会去把那题做完。

现在已知这些题目对于小Y的读题时间和做题时间,而小Y的读题顺序是任意的,求小Y最少可能的罚时之和。

第一行是一个正整数,表示题目数量。接着有$N$($1 \le N \le 10^5$) 行,每行有两个正整数$A_i$ $B_i$,($1 \le A_i;B_i \le 10^5$)分别表示每题的读题时间和做题时间。

输出一个正整数,表示小Y 的最少罚时。

复制
3
1 2
1 3
1 4
24
复制
3
2 3
1 5
3 1
30

样例1中,先读第一题和第二题,于是会做花时间较少的第一题(4),再读第三题,做第二题(8),最后做第三题(12),罚时4+8+12=24。

样例2中,顺序可以为:读第二题->读第三题->做第三题->读第一题->做第一题->做第二题。

2018

埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛