输送物资

掩体搭好了，CC带队冲了过去——4个炮台被挡住，剩下的火力她用金属肩膀硬扛。

"过了。"她喘着气，肩膀上有三道新划痕，"但弹药不够了。"

"要补给。"

"对。"她说，"矿区还有一批物资——能源块、医疗包、备用零件。要运到核心区。"

"路远？"

"远。"她说，"中间有塌方，有哨兵，有辐射区。"

"那咋运？"

"分段运。"你说，"用斜率优化DP。设$dp[i]$为运到第$i$个中转站的最小成本。"

"成本？"

"时间和风险。"你说，"每段路有一个运输成本——距离乘以危险系数。"

"$dp[i]=\min(dp[j]+cost(j,i))$。"

"对。"你说，"$cost(j,i)=(d_i-d_j)\times(risk_j+risk_i)$。"

"这式子能优化？"

"能。"你说，"展开：$dp[i]=\min(dp[j]+d_i\times risk_j+d_i\times risk_i-d_j\times risk_j-d_j\times risk_i)$。"

"按$j$整理：$dp[j]-d_j\times risk_j-d_j\times risk_i$。"

"不对。"你说，"应该是$dp[j]+d_i\times risk_i-d_j\times risk_j-d_j\times risk_i$。"

"把不含$j$的提出来：$d_i\times risk_i+\min(dp[j]-d_j\times risk_j-d_j\times risk_i)$。"

"还是两个变量。"

"但如果按$d_j$排序。"你说，"可以维护下凸壳，用斜率优化。"

"假设$risk_i$是单调的。"

"对。"

你开始写。按$risk$排序，维护凸包。

"第一个中转站。"你说，"距离10，危险系数2。"

"第二个。"你说，"距离25，危险系数1。"

"从起点到第二个。"你说，"成本$=25\times(2+1)=75$。"

"从第一个到第二个。"你说，"成本$=15\times(2+1)=45$。加上到第一个的20，总65。"

"分段更省。"

"对。"你说，"多设中转站，降低每段的风险乘积。"

"但中转站也要人力守。"

"那就是另一个约束了。"你说，"总人力有限，要在运输成本和守卫成本之间平衡。"

"复杂。"

"复杂。"你说，"但可算。"

CC把物资清单折好，塞进金属腰带的夹层里。

"算好了告诉我。"她说，"我先去探路。"

"你一个人？"

"我跑得快。"她说，"而且我认得路——哪些塌方是新塌的，哪些是旧塌的。"

"小心。"

"放心。"她说，"我能打。"

题目描述

给定$n$个中转站，第$i$个距离起点$d_i$，危险系数$r_i$。从起点到终点，必须经过若干中转站。从$j$到$i$的运输成本为$(d_i-d_j)\times(r_j+r_i)$。求最小总成本。

输入格式

$n$。然后$n$行，每行$d_i,r_i$。

输出格式

最小总成本。

输入样例

5
1 2 3 4 5

输出样例

4557430888798830399

提示

• 斜率优化DP。
• $dp[i]=\min(dp[j]+(d_i-d_j)\times(r_j+r_i))$。
• 展开后按$j$整理，维护下凸壳。
• 注意$r_i$的单调性。