AOJ2603.cpp

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef long long ll;

const ll INF = 1e14;

int S, N, M;
ll P[2048], sum[2048];
pair<ll,int> memo[2048][2048];

ll range(int i, int j) { return P[j] * (j - i) - sum[j] + sum[i]; }

pair<ll,int> dp(int n, int m) {
  if (m == -1) return make_pair(INF, 0);
  if (n <= m) return make_pair(0, n-1);
  if (memo[n][m].first != -1) return memo[n][m];
  pair<ll,int> res = make_pair(INF, 0);
  int from = dp(n-1, m).second, to = dp(n, m+1).second;
  for (int i = from; i <= min(n-1, to); ++i)
    res = min(res, make_pair(dp(i, m-1).first + range(i, n-1), i));
  return memo[n][m] = res;
}

int main() {
  cin >> S >> N >> M;
  vector<int> x(S);
  REP(i,S) cin >> x[i];
  REP(i,N) {
    int t, p; cin >> t >> p;
    P[i] = t - x[p-1];
  }
  sort(P, P+N);
  REP(i,N) sum[i+1] = sum[i] + P[i];
  memset(memo, -1, sizeof(memo));
  cout << dp(N, M).first << endl;
  return 0;
}