便于复习

对于动态规划最复杂的就是状态表示f[i], f[i][j], f[i][j][k] ......
其一，选择合适的维度一般来说每添加一个约束则增加一维
其二，解读状态表示
1.以i结尾的所有方案(选i),这类问题i在选择的时候没有约束条件，只影响自己
例如：数字三角形，最长上升子序列，区间DP，斜率优化，单调队列(最大子序和，烽火传递，绿色通道)
2.选择前i个且满足条件约束的方案(选i或者不选i)，这类问题在选择的时候有约束条件，选择i会影响别人
例如：大盗阿福选择i就不能选择i-1，还有背包问题的体积约束，修剪草坪中不能连续的问题
主要以第二类问题居多，没有列举出来的的多数都是第二类问题
ps: 不对的话再修改吧，动态规划完结的一点小感悟

//t[i] - d[i]表示要接到第i只小猫应该出发的时刻，对t - d排序，给一个饲养员出发的时刻能够接到一些小猫
//由于排序了，所以能接到的小猫也是连续的，用P个饲养员要全部接完不一定要全部使用，将问题转化为了将序列最多分为P段的最小花费
//a1, a2, a3, ... , an表示接到猫的最早出发时刻，提前来了接不到小猫
//如果要接123只小猫，则最早出发时刻为a3，对于猫3刚刚好接到，无需等待
//对于猫1已经早就玩完并等待了a3-a1段时间，5点(a1)就该出发接我刚刚好，结果你7点(a3)来让我等你两个小时(a3-a1)
//同理猫2也已经早就玩完并等待了a3-a2段时间，总的等待时间为：a3 - a3 + a3 - a2 + a3 - a1 = a3 * 3 - (a1 + a2 + a3)
//如果出发的足够晚，就可以使用一个饲养员接走，然而其他的小猫都要等他，所以把那些贪玩的单独晚点接，别让听话的小猫等太久
//最后一段为接走k+1 ~ i的小猫 a[i] * (i-k) - (s[i] - s[k])
//f[i][j] 表示取前i只小猫，用j个饲养员的最小等待时间
//f[i][j] = min(f[k][j-1] + a[i] * (i-k) - (s[i] - s[k]);
//整理得：f[k][j-1] + s[k] = a[i] * k  + f[i][j] - a[i] * i + s[i];
//对应于：        y        =   k  * x  +             b
import java.util.*;
class Main{
    private static long inf = Long.MAX_VALUE;       //最大值不能再用0x3f3f3f3f了现在是long类型了
    private static long[] d, a, s;
    private static long[][] f;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int p = sc.nextInt();
        d = new long[n+1];
        a = new long[m+1];
        s = new long[m+1];
        for(int i = 2; i <= n; i++){
            d[i] = d[i-1] + sc.nextInt();
        }

        for(int i = 1; i <= m; i++){
            int h = sc.nextInt();
            int t = sc.nextInt();
            a[i] = t - d[h];
        }

        Arrays.sort(a, 1, m+1);         //a中存在负数了，0不能参与排序的，所以从1 ~ m+1排序左闭右开
        for(int i = 1; i <= m; i++) s[i] = s[i-1] + a[i];

        f = new long[m+1][p+1];
        for(int i = 1; i <= m; i++){
            for(int j = 0; j <= p; j++){
                f[i][j] = inf;
            }
        }
        int[] q = new int[m+1];
        for(int j = 1; j <= p; j++){
            int hh = 0, tt = -1;
            q[++tt] = (int) f[0][j];
            for(int i = 1; i <= m; i++){
                while(hh < tt && (get_y(q[hh+1], j) - get_y(q[hh], j)) <=
                a[i] * (q[hh+1] - q[hh])) hh++;
                int k = q[hh];
                f[i][j] = f[k][j-1] + a[i] * (i-k) - (s[i] - s[k]);
                while(hh < tt && (get_y(i, j) - get_y(q[tt], j)) * (q[tt] - q[tt-1]) <=
                                (get_y(q[tt], j) - get_y(q[tt-1], j)) * (i - q[tt])) tt--;
                q[++tt] = i;
            }
        }
        System.out.println(f[m][p]);
    }

    private static long get_y(int k, int j){
        return f[k][j-1] + s[k];
    }
}