(资料图片仅供参考)

N头牛在花园吃花，约翰将每头牛运回牛舍并回到花园需要时间为2* Ti ，每头牛在被运往牛舍之前每分钟吃 Di 朵花，约翰每次只能运送一头牛回到牛舍，编写一个程序来确定约翰运送奶牛的顺序，使得被吃掉的花总数最少

输入

第 1 行：单个整数 N 行 2..N+1：每行包含两个空格分隔的整数，Ti 和 Di，用于描述一头奶牛的特征

输出

第 1 行：单个整数，即被毁花的最小数量

示例输入

63 12 52 33 24 11 6

示例输出

86

解析

因为我们希望牛吃的花数量最少，所以我们应该优先送回那些吃的花比较 “多” 的牛，这个“多”是个相对的概念，不是单纯的哪头牛吃的更“快”

举个例子：在只有两头牛c1和c2的情况下，D1=7、T1=7，D2=2、T2=1

先送c1回牛舍被吃掉的花数为2×T1×D2=28，先送c2回牛舍被吃掉的花数为2×T2×D1=14。显然先送c2回牛舍是更好的选择，也就是说    T1×D2<T2×D1的时候，我们认为c1吃花吃的更多

有了这个思路，就可以对所有的牛进行一个吃花多少的降序排列，但是又有另一个问题 “公式中的时间T，在多个牛排序中是不同的” 比如三个牛进行比较时比较的是T1×D2、T2×D1和T2×D3、T3×D2 花和时间都变了，可以像只有两头牛那样比较吗？也是可以的，下面给出证明:

题目链接：poj.org/problem?id=3262

关键词：