斜率优化$DP$ + 二分查找  时间复杂度：$O(N*logN)$  

与 $任务安排2(cogs 1162)$ 一题不同的是，$T$ 可能是负数，意味着 $sumT$ 不再具有单调性，从而需要最小化截距的直线斜率 $S+sumT[i]$ 不具有单调性。故，不能在单调队列中只保留凸壳上“$ 连接相邻两点的线段斜率 $”大于 $S+sumT[i]$ 的部分，而是必须维护整个凸壳。

这样一来，就不需要在队头把斜率与 $S+sumT[i]$ 比较。

队头也不一定是最优决策，我们可以在单调队列中二分查找，求一个位置 $p$，$p$ 左侧线段斜率比 $S+sumT[i]$

小，右侧斜率比 $S+sumT[i]$ 大，$p$ 就是最优决策。

队尾维护斜率单调性的方法与 $任务安排2$ 一题相同。