调度任务

序列切完了，但每段内部的任务还要调度——哪些先做，哪些后做，哪些可以并行。

"像工厂。"CC说，"多个机床，多个零件，要排顺序。"

"对。"你说，"但我们不是工厂。我们是反抗军。"

"反抗军也要排顺序。"CC说，"谁先上，谁后上，谁掩护。"

"那咋排？"

"斜率优化。"你说，"每个任务有截止时间$T_i$和惩罚$F_i$。如果超时，惩罚累加。我们要排一个顺序，让总惩罚最小。"

"斜率？"

"对。"你说，"$dp[i]$为前$i$个任务的最小惩罚。$dp[i]=\min(dp[j]+F_i\times(T_i-T_j))$。"

"这能优化？"

"能。"你说，"把式子改写成$y=kx+b$的形式。每个$j$对应一个点$(T_j,dp[j])$，要找斜率$F_i$的直线，截距最小。"

"凸包？"

"对。"你说，"维护下凸壳，用单调队列找最优决策点。"

你开始写。先把任务按$T_i$排序，然后维护凸包。

"第一个任务。"你说，"$T=5,F=3$。"

"第二个。"你说，"$T=8,F=2$。"

"第三个。"你说，"$T=12,F=4$。"

"如果按1,2,3的顺序。"你说，"总惩罚$=0+0+4\times(12-8)=16$。"

"如果按2,1,3。"你说，"总惩罚$=0+3\times(5-5)+4\times(12-8)=16$。"

"如果按1,3,2。"你说，"总惩罚$=0+0+2\times(8-5)=6$。"

"最优是1,3,2？"

"不对。"你说，"3的$F$比2大，应该先做这个——惩罚系数大的先做。"

"那就是按$F$降序。"

"对。"你说，"$F$大的先做，减少它对后面任务的影响。"

"这就是斜率优化的直觉。"

"对。"你说，"直觉背后有数学。"

CC把任务列表刻在金属手臂上——用刀尖刻的，歪歪扭扭。

"刻这干啥子？"

"怕忘。"她说，"打仗的时候，脑子会空白。"

"你不会忘。"

"我会。"她说，"所以我刻下来。"

题目描述

给定$n$个任务，第$i$个有截止时间$T_i$和惩罚系数$F_i$。要安排一个执行顺序。如果任务$i$在$t$时刻完成且$t>T_i$，惩罚为$F_i\times(t-T_i)$。求最小总惩罚。

输入格式

$n$。然后$n$行，每行$T_i,F_i$。

输出格式

最小总惩罚。

输入样例

5
1 2 3 4 5

输出样例

311

提示

• 斜率优化DP。
• $dp[i]$为前$i$个任务的最小惩罚。
• 任务按$T$排序后，$dp[i]=\min(dp[j]+F_i\times(T_i-T_j))$。
• 维护下凸壳，单调队列优化。