菜鸡求助

#define Love_Icy 1
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define LL long long

using namespace std;

template <typename T>inline void read(T &x)
{
	T ch=getchar(),xx=0,fw=1;
	while(!isdigit(ch)){if(ch=='-')fw=-1;ch=getchar();}
	while(isdigit(ch)){xx=(xx<<1)+(xx<<3)+ch-'0';ch=getchar();}
	x=fw*xx;
}

template <typename T>inline void prt(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)prt(x/10);
	putchar(x%10+'0');
	return ;
}

int n,m,p;
LL dis[500010],D[500010];
LL H[500010],T[500010];
LL t[500010],sl[500010];
LL f[210][500010],ans;

inline LL ry(int i,int k){return f[i-1][k]+sl[k];}
inline LL rb(int i,int j){return f[i][j]+sl[j]-j*t[j];}
inline LL gb(int i,int j,int k){return ry(i,k)-k*t[j];}
//inline ll rkx(int i,int k){return k*t[j];}
inline LL cslp(LL a,LL b,LL c,int i)
{
	LL X1=a-b,X2=b-c,Y1=ry(a,i)-ry(b,i),Y2=ry(b,i)-ry(c,i);
	return X1*Y2-X2*Y1;
}

int main(void)
{
	read(n);read(m);read(p);
	for(int i=1;i<n;i++)read(D[i]);
	dis[1]=0;
	for(int i=2;i<=n;i++)dis[i]=dis[i-1]+D[i-1];
//	for(int i=1;i<=n;i++)printf("%d ",dis[i]);
	for(int i=1;i<=m;i++){read(H[i]);read(T[i]);}
	for(int i=1;i<=m;i++)t[i]=T[i]-dis[H[i]];
	sort(t+1,t+1+m);
	for(int i=1;i<=m;i++)sl[i]=sl[i-1]+t[i];
	for(int i=1;i<=m;i++)f[1][i]=t[i]*i-sl[i];
	
	int head,tail;
	int squ[100010];
	ans=f[1][m];
//	for(int i=1;i<=n;i++)printf("%d ",dis[i]);
	for(int i=2;i<=p;i++){
		head=1;tail=0;
		squ[++tail]=0;
		for(int j=1;j<=m;j++){
			while(head<tail && gb(i,j,squ[head])>gb(i,j,squ[head+1]))head++;
			f[i][j]=f[i-1][squ[head]]+(j-squ[head])*t[j]-sl[j]+sl[squ[head]];
//			f[i][j]=ry(i,squ[head])+j*t[j]-sl[j]-squ[head]*t[j];
			while(head<tail && cslp(j,squ[tail],squ[tail-1],i)>0)tail--;
			squ[++tail]=j;
		}
		ans=min(ans,f[i][m]);
	}
	printf("%lld",ans);
    return 0;
}