错峰调度

"8批。"你说，"总时间47。"

"47小时？"Echo问。

"47分钟。"你说，"子系统重启很快，主要是同步时间。"

"同步？"

"对。"你说，"每批重启后，要等所有子系统同步，才能启动下一批。"

"等多久？"

"看负载。"你说，"如果多批同时同步，总线会拥堵。所以要错峰——让同步时间错开。"

"错峰调度。"

"对。"你说，"设$dp[i]$为前$i$批的最短总时间。$dp[i]=\min(dp[j]+sync\_time(j+1,i)+batch\_time(i))$。"

"$sync\_time$是同步时间。"

"对。"你说，"如果两批的同步时间重叠，会互相干扰，总同步时间增加。"

"所以要错峰——让同步时间不重叠。"

"对。"你说，"用斜率优化。把同步时间看成二次函数，找最优的错峰间隔。"

"二次函数？"

"对。"你说，"$sync\_time=a\times x^2+b\times x+c$，其中$x$是间隔。最小值在$x=-b/(2a)$。"

"那最优间隔是固定的？"

"对。"你说，"如果负载均匀，最优间隔是常数。"

"那我们就按这个间隔排。"

"对。"

你开始写。先算最优间隔，然后按间隔分批。

"最优间隔。"你说，"3分钟。"

"第一批，0到5分钟。"

"第二批，8到13分钟。"（间隔3分钟）

"第三批，16到21分钟。"

"……"

"第八批，45到50分钟。"

"总时间50分钟。"

"比不分错峰的47分钟还长？"

"对。"你说，"但负载更均匀，不会拥堵。"

"不会拥堵意味着——"

"意味着不会出错。"你说，"出错一次，重启时间翻倍。"

"那就50分钟。"

"对。"你说，"50分钟，稳。"

Echo把错峰表发给所有子系统。光点开始按节奏闪烁——不是随机的，是有韵律的，像心跳。

"它们在呼吸。"Echo说。

"对。"你说，"它们在同步。"

"同步之后呢？"

"之后。"你说，"就是最后一战。"

"最后一战？"

"对。"你说，"下一章，DP实战。"

"实战。"

"对。"你说，"把所有DP优化，用在最后的战场上。"

Echo的投影在同步的光中，比以往任何时候都更稳定——不是因为她得到了更多能源，是因为她找到了节奏。

"我准备好了。"她说。

"我们也准备好了。"你说。

题目描述

给定$n$批任务，每批有一个处理时间和同步时间。如果两批的同步时间重叠，总同步时间增加。求错峰调度的最短总完成时间。

输入格式

$n$。然后$n$行，每批的处理时间$p_i$和同步时间$s_i$。

输出格式

最短总完成时间。

输入样例

5
1 2 3 4 5

输出样例

311

提示

• 斜率优化DP。
• $dp[i]$为前$i$批的最短时间。
• $dp[i]=\min(dp[j]+cost(j+1,i))$，其中$cost$包括处理时间和错峰同步时间。
• 把$cost$展开成二次函数形式，用斜率优化。