RT，调几天了 /kk

#include <bits/stdc++.h>
#define int long long
// FOR templates.
#define rep(i, s, n, k) for(int i = s;i <= n;i += k)
#define repn(i, s, n, k) for(int i = s;i < n;i += k)
#define pre(i, s, n, k) for(int i = s;i >= n;i -= k)
#define pren(i, s, n, k) for(int i = s;i > n;i -= k)
// Abbr for STL.
#define pii pair<int, int>
#define pdd pair<double, double>
#define mpi map<int, int>
#define vc vector<int>
// IO templates, proven very useful.
#define cn(n) int n;cin >> n
#define cm(n) cin >> n
// Abbr for funcs.
#define pb push_back
#define mset memset
// #define files
using namespace std;
const int MAXN = 0x3f3f3f3f3f3f3f3fLL;
const int MOD1 = 1000000007LL;
const int MOD2 = 998244353LL;
// int d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int gcd(int a, int b) {if(b == 0) return a;return gcd(b, a % b);}
inline int lowbit(int x) {return x & (-x);}
inline int lcm(int a, int b) {return a * b / gcd(a, b);}
 
int dp[100001][101], d[100001], h[100001], t[100001];
int st[100001], l, r; pii q[100001];
 
int slope(int s){
	return t[s];
}
bool check(pii x, pii y, int s){
	return (y.second - x.second) <= slope(s) * (y.first - x.first);
}
bool check1(pii x, pii y, pii z){
	return (y.second - x.second) * (z.first - y.first) >= (z.second - y.second) * (y.first - x.first);
}
 
 
signed main(){
#ifdef files
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cn(n); cn(m); cn(p);
	rep(i, 2, n, 1) cm(d[i]);
	rep(i, 1, m, 1) cin >> h[i] >> t[i];
	rep(i, 2, n, 1) d[i] += d[i - 1];
	rep(i, 1, m, 1){
		st[i] = t[i]; st[i] -= d[h[i]];
	}
	rep(i, 1, m, 1) t[i] = st[i];
	sort(st + 1, st + m + 1);
	rep(i, 1, m, 1) st[i] += st[i - 1];
	mset(dp, MAXN, sizeof(dp));
	dp[0][0] = 0LL;
	rep(j, 1, p, 1){
		int l = 1, r = 1; q[1] = make_pair(0, dp[0][j - 1] + st[0]);
		rep(i, 1, m, 1){
			while(l < r && check(q[l], q[l + 1], i)) l++;
			dp[i][j] = dp[q[l].first][j - 1] + t[i] * (i - q[l].first) - st[i] + st[q[l].first];
			pii p = make_pair(i, dp[i][j - 1] + st[i]);
			while(l < r && check1(q[r - 1], q[r], p)) r--;
			q[++r] = p;
		}
	}
	cout << dp[m][p] << endl;
	return 0;
}
 
/*
 *  things to check
 *  1.  int overflow or long long memory need
 *  2.  recursion/array/binary search/dp/loop bounds
 *  3.  precision
 *  4.  special cases(n=1,bounds)
 *  5.  delete debug statements
 *  6.  initialize(especially multi-tests)
 *  7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
 *  8.  keep it simple and stupid
 *  9.  do not delete, use // instead
 *  10. operator priority
 *  11. is there anything extra to output?
 *  12. THINK TWICE CODE ONCE, THINK ONCE DEBUG FOREVER
 *  13. submit ONCE, AC once. submit twice, WA forever
 *  14. calm down and you'll get good rank
 *  15. even a bit wrong scores zero
 *  16. ...
 **/