$A_i=T_i-\sum_{j=1}^{H_i}D_j$也就是饲养员至少要从第$A_i$个时刻之后出发，才能接到$i$的。

根据贪心，肯定是接连续的一段$A_i$更优，因此将$A_i$从小到大排序。

那么$f_{i,j}$表示前$i$个管理员接到前$j$只猫的最短等待时间。

有$f_{i,j}=\min\limits_{0\le k\le j}\{f_{i-1,k}+\sum_{p=k+1}^j(A_{max~A[q\in[k+1,j]]}-A_p)\}$

变为:$f_{i,j}=\min\limits_{0\le k\le j}\{f_{i-1,k}+\sum_{p=k+1}^j(A_{j}-A_p)\}$

记录$A_i$的前缀和$S_i$，那么有$\sum_{p=k+1}^j(A_{j}-A_p)=A_j*(j-k)-(S_j-S_k)$

乱搞之后可以发现，$f_{i,j}=\min\limits_{0\le k\le j}\{f_{i-1,k}+A_j*(j-k)-(S_j-S_k)\}$

转为一条关于$f_{i-1,k}+S_k=A_j*k+f_{i,j}-A_j*j+S_j$的直线。

当截距最小时即为$f_{i,j}$的最小值。

由于斜率不断递增，那么此时就要维护一个下凸壳来满足这个性质。

具体来讲就是对于$k_1<k_2<k_3$，需满足

$\large\frac{f_{i-1,k_2}-f_{i-1,k_1}+S_{k_2}-S_{k_1}}{k_2-k_1}<\frac{f_{i-1,k_3}-f_{i-1,k_2}+S_{k_3}-S_{k_2}}{k_3-k_2}$

队头要满足$\large\frac{f_{i-1,q[l+1]}-f_{i-1,q[l]}+S_{q[l+1]}-S_{q[l]}}{q[l+1]-q[l]}>A_j$，即在当前斜率下，队头是最优的。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+10;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll s[N],a[N],d[N],f[2][N];int q[N],u,v;
bool slope(int i,int j,int k){return (f[v][j]+s[j]-f[v][i]-s[i])*(k-j)>=(f[v][k]+s[k]-f[v][j]-s[j])*(j-i);}
int main()
{
    int n,m,p;qr(n),qr(m),qr(p);
    d[1]=0;for(int i=2;i<=n;i++)qr(d[i]),d[i]+=d[i-1];
    for(int i=1,h,t;i<=m;i++)
    {
        qr(h),qr(t);a[i]=t-d[h];
        //s[i]=s[i-1]+a[i];
    }
    sort(a+1,a+m+1);
    for(int i=1;i<=m;i++)s[i]=s[i-1]+a[i];
    u=1;v=0;
    for(int i=1;i<=m;i++)
        f[1][i]=a[i]*i-s[i];
    swap(u,v);
    for(int i=2;i<=p;i++,swap(u,v))
    {
        int l=1,r=1;q[1]=0;
        for(int j=1;j<=m;j++)
        {
            while(l<r&&f[v][q[l+1]]+s[q[l+1]]-f[v][q[l]]-s[q[l]]<=a[j]*(q[l+1]-q[l]))++l;
            f[u][j]=f[v][q[l]]+a[j]*(j-q[l])-(s[j]-s[q[l]]);
            while(l<r&&slope(q[r-1],q[r],j))--r;
            q[++r]=j;
        }
    }
    qw(f[v][m]);puts("");
    return 0;
}