Zxr960115 is owner of a large farm. He feeds m cute cats and employs p feeders. There's a straight road across the farm and n hills along the road, numbered from 1 to n from left to right. The distance between hill i and (i - 1) is di meters. The feeders live in hill 1.

One day, the cats went out to play. Cat i went on a trip to hill hi, finished its trip at time ti, and then waited at hill hi for a feeder. The feeders must take all the cats. Each feeder goes straightly from hill 1 to n without waiting at a hill and takes all the waiting cats at each hill away. Feeders walk at a speed of 1 meter per unit time and are strong enough to take as many cats as they want.

For example, suppose we have two hills (d2 = 1) and one cat that finished its trip at time 3 at hill 2 (h1 = 2). Then if the feeder leaves hill 1 at time 2 or at time 3, he can take this cat, but if he leaves hill 1 at time 1 he can't take it. If the feeder leaves hill 1 at time 2, the cat waits him for 0 time units, if the feeder leaves hill 1 at time 3, the cat waits him for 1 time units.

Your task is to schedule the time leaving from hill 1 for each feeder so that the sum of the waiting time of all cats is minimized.

Input

The first line of the input contains three integers n, m, p (2 ≤ n ≤ 105, 1 ≤ m ≤ 105, 1 ≤ p ≤ 100).

The second line contains n - 1 positive integers d2, d3, ..., dn (1 ≤ di < 104).

Each of the next m lines contains two integers hi and ti (1 ≤ hi ≤ n, 0 ≤ ti ≤ 109).

Output

Output an integer, the minimum sum of waiting time of all cats.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12


Output

3
#include <bits/stdc++.h>
using namespace std;
void read(bool out = 0) {}
const long long Q = -(1ll << 60);
struct line {
  long double m, p;
  mutable set<line>::iterator prev;
};
set<line>::iterator null;
bool operator<(const line &a, const line &b) {
  if (b.p != Q && a.p != Q) {
    return a.m > b.m;
  }
  if (b.p == Q) {
    if (a.prev == null) return true;
    bool ok = true;
    if ((a.prev->m - a.m) < 0) ok = !ok;
    if (ok)
      return (a.p - a.prev->p) < (a.prev->m - a.m) * b.m;
    else
      return (a.p - a.prev->p) > (a.prev->m - a.m) * b.m;
  } else {
    if (b.prev == null) return false;
    bool ok = true;
    if ((b.prev->m - b.m) < 0) ok = !ok;
    if (ok)
      return !((b.p - b.prev->p) < a.m * (b.prev->m - b.m));
    else
      return !((b.p - b.prev->p) > a.m * (b.prev->m - b.m));
  }
}
class convex_hull {
 public:
  set<line> convex;
  set<line>::iterator next(set<line>::iterator ii) {
    set<line>::iterator gg = ii;
    gg++;
    return gg;
  }
  set<line>::iterator prev(set<line>::iterator ii) {
    set<line>::iterator gg = ii;
    gg--;
    return gg;
  }
  bool bad(set<line>::iterator jj) {
    set<line>::iterator ii, kk;
    if (jj == convex.begin()) return false;
    kk = next(jj);
    if (kk == convex.end()) return false;
    ii = prev(jj);
    line a = *ii, c = *kk, b = *jj;
    bool ok = true;
    if ((b.m - a.m) < 0) ok = !ok;
    if ((b.m - c.m) < 0) ok = !ok;
    if (ok)
      return (c.p - b.p) * (b.m - a.m) <= (a.p - b.p) * (b.m - c.m);
    else
      return (c.p - b.p) * (b.m - a.m) >= (a.p - b.p) * (b.m - c.m);
  }
  void del(set<line>::iterator ii) {
    set<line>::iterator jj = next(ii);
    if (jj != convex.end()) {
      jj->prev = ii->prev;
    }
    convex.erase(ii);
  }
  void add(long long m, long long p) {
    null = convex.end();
    line g;
    g.m = m;
    g.p = p;
    set<line>::iterator ii = convex.find(g);
    if (ii != convex.end()) {
      if (ii->p <= p) return;
      del(ii);
    }
    convex.insert(g);
    ii = convex.find(g);
    set<line>::iterator jj = next(ii);
    if (jj != convex.end()) jj->prev = ii;
    if (ii != convex.begin())
      ii->prev = prev(ii);
    else
      ii->prev = convex.end();
    if (bad(ii)) {
      del(ii);
      return;
    }
    jj = next(ii);
    while (jj != convex.end() && bad(jj)) {
      del(jj);
      jj = next(ii);
    }
    if (ii != convex.begin()) {
      jj = prev(ii);
      while (ii != convex.begin() && bad(jj)) {
        del(jj);
        jj = prev(ii);
      }
    }
  }
  long long query(long long x) {
    null = convex.end();
    line y;
    y.m = x;
    y.p = Q;
    if (convex.size() == 0) {
      return (1ll << 61);
    }
    set<line>::iterator iii = convex.lower_bound(y);
    iii--;
    return iii->m * x + iii->p;
  }
};
class ConvexHullTrick {
 public:
  long long M[200003];
  long long B[200003];
  long long I[200003];
  int si;
  int pt;
  ConvexHullTrick() {
    si = 0;
    pt = 0;
  }
  void init() {
    si = 0;
    pt = 0;
  }
  bool bad(int a, int b, int c) {
    return (B[b] - B[a]) * (M[a] - M[c]) >= (B[c] - B[a]) * (M[a] - M[b]);
  }
  void add(long double m, long double b, int ind) {
    M[si] = m;
    B[si] = b;
    I[si] = ind;
    si++;
    while (si >= 3 && bad(si - 3, si - 2, si - 1)) {
      M[si - 2] = M[si - 1];
      B[si - 2] = B[si - 1];
      I[si - 2] = I[si - 1];
      si--;
    }
    if (pt >= si) {
      pt = si - 1;
    }
  }
  long double query(long double x) {
    if (si == 0) {
      return 1ll << 60;
    }
    if (pt >= si) {
      pt = si - 1;
    }
    while (pt < si - 1 && M[pt + 1] * x + B[pt + 1] < M[pt] * x + B[pt]) {
      pt++;
    }
    return M[pt] * x + B[pt];
  }
};
ConvexHullTrick conv[3];
long long d[100009];
long long h[100009], t[100009];
long long a[100009];
long long dis[100009];
long long sum[100009] = {};
long long dp[100009][100];
int main() {
  read();
  long long n, m, p;
  cin >> n >> m >> p;
  for (int i = 1; i < n; i++) {
    cin >> d[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> h[i] >> t[i];
  }
  dis[0] = 0;
  sum[0] = 0;
  for (int i = 1; i < n; i++) {
    dis[i] = dis[i - 1] + d[i];
  }
  for (int i = 0; i < m; i++) {
    a[i] = t[i] - dis[h[i] - 1];
  }
  sort(a, a + m);
  for (int i = 0; i < m; i++) {
    sum[i] = a[i] + (i != 0) * sum[i - 1];
  }
  bool table = 0;
  for (int k = 0; k <= p; k++, table = !table) {
    conv[table].init();
    if (k == 0) {
      conv[table].add(0, 0, 0);
    } else {
      for (int i = 0; i <= m; i++) {
        if (i == 0) {
          dp[i][k] = 0;
        } else {
          dp[i][k] = conv[!table].query(a[i - 1]) + a[i - 1] * (i)-sum[i - 1];
        }
        conv[table].add(-i, sum[i - 1] + dp[i][k], 0);
      }
    }
  }
  cout << dp[m][p];
}
