You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

爸爸公司的大厦，在早高峰期，几乎每层都有人上下，电梯每层都停，大家被弄的很不耐烦，阳阳提出一个解决办法：每次电梯从一层往上走时，只允许电梯停在其中的某一层，所有乘客从一楼上电梯，到达某一层后，电梯停下来，所有乘客再从这里走楼梯到自己的目的楼层。为了对要去的某一个楼层人数计数，电梯的按钮做了特殊的改造，每个人上电梯按一下自己所要去的楼层，电梯可以统计目标楼层的人数。我们要给电梯编写一个附加特别程序，根据大家在一楼按下的目的楼层，计算电梯应该停在某层，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少。求这个最小值。

输入格式

第一行，一个正整数N，表示需要到达的目标楼层的数。

以下N行，每行两个整数，分别表示要到达的目标楼层和需要到达目标楼层的人数。

输出格式

一个整数，意义如题所述。

输入样例

5

5 4

8 10

20 3

19 9

2 2

输出样例

159

数据范围

1<=N<=100000

提示说明

N个乘客只会从一楼进入电梯，进入电梯后必须等到电梯停在某一层才会出电梯，若有需要，在爬楼梯到达自己的目标楼层。