题目描述

农夫约翰像往常一样去砍木头，留下了N（2 ≤ N ≤ 100,000）头奶牛在吃草。当他回来时，惊恐地发现这群奶牛正在他的花园里吃他美丽的花。为了最小化后续的损失，约翰决定立即采取行动，把每头奶牛送回各自的牛棚。

每头奶牛i所在的位置距离自己的牛棚需要Ti分钟（1 ≤ Ti ≤ 2,000,000）。此外，在等待运输的过程中，它每分钟会毁掉Di（1 ≤ Di ≤ 100）朵花。无论约翰怎么努力，他一次只能运输一头奶牛回牛棚。将奶牛i运到牛棚需要2×Ti分钟（去需要Ti分钟，回来也需要Ti分钟）。约翰从花田出发，把奶牛运到牛棚，然后走回花田，前往下一头需要运输的奶牛时不花费额外时间。

编写一个程序，确定约翰运输奶牛的顺序，使得被毁掉的花的总数最少。

输入格式

第1行：一个整数N
第2到N+1行：每行包含两个用空格分隔的整数Ti和Di，表示一头奶牛的特征

输出格式

第1行：一个整数，表示被毁掉的花的最小数量

输入数据1

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

输出数据1

86  

提示

约翰按以下顺序运输奶牛：6、2、3、4、1、5。当他运输奶牛6到牛棚时，其他奶牛毁掉了24朵花；接下来运输奶牛2，又损失了28朵花；运输奶牛3、4、1时，分别损失16、12和6朵花；运输奶牛5时，已经没有其他奶牛在毁花了，所以这头奶牛造成的损失为0。这种方式下总共损失的花为24 + 28 + 16 + 12 + 6 = 86。

题目来源

USACO 2007 年1月银奖