Problem C: PIPI非洲行

Problem C: PIPI非洲行

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 435  Solved: 85
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI最近去了撒哈拉大沙漠探索绿洲,那里只有孤漠和天空。
PIPI在渴了2天后终于发现了一个部落,部落里有唯一的一口水井,全部落的人每天都要来这里排队打水。
众所周知,非洲部落有等级制度,所以每个人都有一个特权值Pi,同时每个人的需水量不同,所以每个人都有一个接水时间Ti。
PIPI来到接水口时,已经有n个人排好了队,但好客的酋长同意给PIPI一次重新安排队列顺序的机会。
请你帮PIPI重新安排队列,使得(每个人从开始排队到接完水的总时间*自身特权值)的总和最小。

Input

一个整数n,表示排队接水的人数,n<=100000
接下来n行,每行两个整数Pi,Ti,分别表示特权值和接水时长,0<=Pi,Ti<=1000.

Output

输出一个整数,表示答案。

Sample Input

4
1 4
2 3
3 2
4 1

Sample Output

35