码蚁编程 Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

2080: 赶牛

内存限制：128 MB 时间限制：1.000 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：4
提交提交记录统计Web Board

题目描述

农夫约翰家的N头牛在花园里大肆破坏，需要将他们赶紧赶回去。第i头牛到牛棚之间的距离要花费的时间为2*Ti，在第i头牛还没被赶回去之前，它会以每分钟Di的速度破坏花园。约翰一次只能弄回去一头牛。农夫约翰从牛棚到牛身边花费的时间忽略不计。请帮助约翰计算损失D最小能减少到多少。

输入格式

第一行，一个整数，N
接下来N行，第i行两个整数，Ti Di

输出格式

输出最小的总破坏D

输入样例 复制 

6
3 1
2 5
2 3
3 2
4 1
1 6

输出样例 复制 

86

数据范围与提示

2 ≤ N ≤ 100,000
1 ≤ Ti ≤ 2,000,000
1 ≤ Di ≤ 100