看到没有人写李超线段树的解法，过来写一篇。

李超线段树是一种维护直线的数据结构，它支持插入一条解析式为 $kx+b$ 的直线，并查询所有直线中在 $x=a$ 时 $y$ 值最小的一条。

李超线段树通过维护每个区间中点最小的直线来做到这一点，具体过程可以看 我的李超线段树学习笔记。

李超线段树与斜率优化本质基本相同，但在解决一些没有单调性的斜优问题时写李超线段树可以避免恶心的动态凸包。

考虑这一题，其实 dp 柿子不是很好列，需要一种思想，即在计算当前的状态时提前统计当前状态对之后的贡献，这里可以参考 P2466 [SDOI2008] Sue 的小球。

设 $sumt_i = \sum_{j=1}^i T_j$ ， $sumv_i=\sum_{j=1}^iC_j$ ，$F_i$ 为以 $i$ 为一段区间右端点的最小代价。

枚举 $j$ 做为上一个区间的右端点，可以列出柿子：

$F_i=min_{j=0}^{i-1}(F_j+sumt_i\times(sumv_i-sumv_j)+s\times(sumv_n-sumv_j))$

这里提前计算了启动时间 $s$ 对之后所有任务的影响。

使用李超线段树维护 dp 柿子时需要将柿子化为 $F=kx+b$ 的形式，其中 $k$ 和 $b$ 只与 $j$ 有关，$x$ 只与 $i$ 有关，所以我们将柿子拆开。

设 $lasv_i=sumv_n-sumv_i$ ，

$F_i=min_{j=0}^{i-1} (F_j + sumt_i\times sumv_i -sumt_i\times sumv_j+s\times lasv_j)$

将 $sumt_i \times sumv_i$ 这个项提到外面去：

$F_i=min_{j=0}^{i-1} (F_j -sumt_i\times sumv_j+s\times lasv_j) + sumt_i\times sumv_i$

发现 $F_j -sumt_i\times sumv_j+s\times lasv_j$ 即为函数 $f_j(x)=kx+b=(-sumv_j) x+(F_j+s\times lasv_j)$ 在 $x=sumt_i$ 处的取值。

通过查询李超线段树中在 $x=sumt_i$ 时最低的直线来 dp，并在计算完每个 $i$ 的 dp 值后，将 $f_i(x)=(-sumv_i) x+(F_i+s\times lasv_i)$ 这条直线插入李超线段树即可。

李超线段树的大小为值域大小，但是 $sumt_i$ 的值域太大。发现询问点只有 $n$ 个，因此将询问点排序并离散化，维护每个询问点处最低的直线即可。

$Code$

// Problem: P2608 [ZJOI2010] 任务安排
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2608
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define N 300010
#define ls k*2
#define rs k*2+1
#define mid (l+r)/2
#define int long long
using namespace std;
int read() {
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
	return f*res;
}
int k[N],b[N],d[N<<2],n,s,dp[N],t[N],v[N],tmp[N],tn,pos[N];
int f(int x,int id) {return k[id]*x+b[id];}
void update(int k,int l,int r,int id) {
	if(l==r) {
		if(f(tmp[l],id)<f(tmp[l],d[k])) d[k]=id;
		return ;
	}
	if(f(tmp[mid],id)<f(tmp[mid],d[k])) swap(id,d[k]);
	if(f(tmp[l],id)<f(tmp[l],d[k])) update(ls,l,mid,id);
	else if(f(tmp[r],id)<f(tmp[r],d[k])) update(rs,mid+1,r,id);
}
int query(int k,int l,int r,int x) {
	if(l==r) return f(tmp[x],d[k]);
	return min(f(tmp[x],d[k]),x<=mid?query(ls,l,mid,x):query(rs,mid+1,r,x));
}
signed main()
{
 	n=read(),s=read(),b[0]=1e18;
 	for(int i=1; i<=n; i++) t[i]=read()+t[i-1],tmp[++tn]=t[i],v[i]=read()+v[i-1];
 	sort(tmp+1,tmp+n+1),tn=unique(tmp+1,tmp+n+1)-tmp-1;
 	for(int i=1; i<=n; i++) pos[i]=lower_bound(tmp+1,tmp+tn+1,t[i])-tmp;
 	dp[1]=t[1]*v[1]+s*v[n],k[1]=-v[1],b[1]=dp[1]+s*(v[n]-v[1]);
 	update(1,1,tn,1);
 	for(int i=2; i<=n; i++) {
 		dp[i]=t[i]*v[i]+s*v[n];
 		dp[i]=min(dp[i],query(1,1,tn,pos[i])+t[i]*v[i]);
 		k[i]=-v[i],b[i]=dp[i]+s*(v[n]-v[i]);
 		update(1,1,tn,i);
 	}
    printf("%lld",dp[n]);
	return 0;
}