首先考虑 $a_i \leftarrow t_i - \sum\limits_{j=2}^i d_{h_i}$，即算出一个铲屎官最早什么时候出发能带走这只猫。
然后就和 $h_i$ 无关了，再把 $t$ 排序，每次相当于选取一段区间，代价是区间每个数与区间最大值差的绝对值之和。
容易想到二维 DP 状态 $dp_{i,j}$ 表示前 $j$ 个分成 $i$ 组的最小代价。

$$dp_{i,j} = \min\limits_{0 \leq k \lt j} \{ dp_{i-1,k} + a_j \times (j-k) - (s_j - s_k) \}$$

这样时间复杂度是 $O(p m^2)$ 的。
然后直接干斜率优化。
仍然设 $k_1 \lt k_2$，$k_1$ 决策优于 $k_2$，推导得到：

$$\frac{(dp_{i-1,k_1} + s_{k_1}) - (dp_{i-1,k_2} + s_{k_2})}{k_1 - k_2} \geq a_j$$

双单增，直接单调队列维护下凸壳，队首转移。
哦耶一遍写对了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15, M = 115;
int n, m, p, d[N], a[N];
long long s[N], dp[M][N];
int q[N], st, ed;

long long x(int p) { return p; }
long long y(int t, int p) { return dp[t][p] + s[p]; }
double slope(int t, int a, int b) {
    return (y(t, a) - y(t, b)) * 1.00 / (x(a) - x(b));
}

int main() {
    scanf("%d%d%d", &n, &m, &p);
    d[1] = 0;
    for (int i = 2; i <= n; i++) scanf("%d", &d[i]), d[i] += d[i - 1];
    for (int i = 1, h, t; i <= m; i++) scanf("%d%d", &h, &t), a[i] = t - d[h];
    sort(a + 1, a + 1 + m);
    for (int i = 1; i <= m; i++) s[i] = s[i - 1] + a[i];
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    for (int i = 1; i <= p; i++) {
        st = ed = 1, q[st] = 0;
        for (int j = 1; j <= m; j++) {
            while (st < ed && slope(i - 1, q[st], q[st + 1]) < a[j]) st++;
            int k = q[st];
            dp[i][j] = dp[i - 1][k] + a[j] * 1ll * (j - k) - (s[j] - s[k]);
            while (st < ed && slope(i - 1, q[ed - 1], q[ed]) >= slope(i - 1, q[ed], j)) ed--;
            q[++ed] = j;
        }
    }
    printf("%lld\n", dp[p][m]);
    return 0;
}