调了一晚上。。。

#include<bits/stdc++.h>
#define ll long long
#define double long double
using namespace std;
const int N = 1e5 + 100;
ll n, m, p, q[4 * N];
ll d[N], a[N], f[205][N], sum[N];
bool com1(int i, ll a, ll b, ll c) {
	//                             a                                     b
//	double k1 = 1.0 * (f[i-1][b] + sum[b] - f[i-1][a] - sum[a]) / ((b-a) == 0 ? 1e-9 : (b-a));
//	                             c                                     d
//	double k2 = 1.0 * (f[i-1][c] + sum[c] - f[i-1][b] - sum[b]) / ((c-b) == 0 ? 1e-9 : (c-b));
	ll k1 = (f[i-1][b] + sum[b] - f[i-1][a] - sum[a]) * (c-b);
	ll k2 = (f[i-1][c] + sum[c] - f[i-1][b] - sum[b]) * (b-a);
	
	return k1 <= k2;
}
bool com2(ll i, ll a, ll b, ll k) {
	//                             a                                     b
//	double k1 = 1.0 * (f[i-1][b] + sum[b] - f[i-1][a] - sum[a]) / ((b-a) == 0 ? 1e-9 : (b-a));
	//                c d
//	double k2 = 1.0 * k/1;
	ll k1 = (f[i-1][b] + sum[b] - f[i-1][a] - sum[a]);
	ll k2 = k * (b-a);
	return k1 <= k2;
}
int main(){
	scanf("%lld%lld%lld", &n, &m, &p);
	for(int i = 2; i <= n; i++) {
	scanf("%lld", &d[i]);
	d[i] += d[i-1];
	}
	for(int i = 1; i <= m; i++) {
		ll h, t;
		scanf("%lld%lld", &h, &t);
		a[i] = t - d[h];
	}
	sort(a + 1, a + m + 1);
	for(int i = 1; i <= m; i++) {
		f[0][i] = 1e18 + 20; 
		sum[i] = sum[i - 1] + a[i];
	}
	
	for(int i = 1; i <= p; i++) {
		ll h = 0, t = -1;
		for(int j = 1; j <= m; j++) {
			while(h < t && com1(i, q[t-1], q[t], j-1) == 1) t--;
			q[++t] = j - 1;
			while(h < t && com2(i, q[h], q[h+1], a[j]) == 1) h++;
			ll k = q[h];
			f[i][j] = f[i-1][k] - sum[j] + sum[k] + a[j] * j - a[j] * k;
		}
	}
	printf("%lld", f[p][m]);
	return 0;
}