凯恩·血蹄--烽火戏诸侯

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 13 总提交人数: 21

题目描述

牛头人酋长为了防御狗头人酋长的进攻,决定从营地到前线一条直线上,修筑一些烽火台来更好地传递消息,他让牛头人考察了许多地点,来决定修筑烽火台的位置。 N只小牛头人带回来了N条考察结果,分别为在距离前线Ai处,若是修烽火台,每修高一米,就要消费Pi 币,同时每修高一米,就使自己被点燃时,在多一单位距离内被看到。当然,只有一个烽火台看到前面有烽火台被点燃时,才会点燃自己而往下传递消息。现在牛头人酋长要从距离前线最近的烽火台,将消息传到距离前线最远的烽火台(这两座烽火台一定要修建),同时呢,也要尽可能少花点钱。 可是麻烦的是,有些小牛头人考察了同一个地点,甚至在同一地点修烽火台他们的价格都可能不同,这使本来就繁多的数据更乱了,于是牛头人酋长找到你,希望你计算出最少花费是多少。

输入

第一行一个数N,表示N个修烽火台位置

接下来N行,每行两个整数Ai,Pi,表示距离前线距离和单位高度(或警示范围)造价

输出

一个数,即最小造价

输入样例

6
1 100000
100 1000
20 80000
40 60000
60 40000
80 100000

输出样例

6300000

在1处修高度19的烽火台,20处修高度20的烽火台,40处修高度20的烽火台,60处修高度40的烽火台,80处不修烽火台,100处修高度为0的烽火台

对于100%的数据,0<N<=200000,0<=Ai<=100000000,0<=Pi<=200000000

相关推荐