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;
auto fio = (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0));
struct Line {
  long long m, p;
  Line(long long m, long long p) : m(m), p(p) {}
  long long eval(long long x) { return m * x + p; }
  double intersectX(Line& o) { return (double)(p - o.p) / (o.m - m); }
};
int32_t main() {
  long long n, m, p;
  cin >> n >> m >> p;
  vector<long long> d(n);
  for (long long i = 1; i < n; i++) cin >> d[i];
  partial_sum(d.begin(), d.end(), d.begin());
  vector<long long> vec(m);
  for (long long i = 0; i < m; i++) {
    long long h;
    cin >> h;
    h--;
    long long t;
    cin >> t;
    vec[i] = t - d[h];
  }
  sort(vec.begin(), vec.end());
  vector<long long> pfx(m), dp(m, 1e17);
  partial_sum(vec.begin(), vec.end(), pfx.begin());
  while (p--) {
    deque<Line> dq;
    dq.push_back(Line(0, 0));
    for (long long i = 0; i < m; i++) {
      long long m = dq.size();
      Line cur(-(i + 1), dp[i] + pfx[i]);
      while (m >= 2 &&
             dq[m - 2].intersectX(cur) <= dq[m - 1].intersectX(dq[m - 2]))
        dq.pop_back(), m--;
      dq.push_back(cur);
      m++;
      long long x = vec[i];
      while (m >= 2 && dq[1].eval(x) <= dq[0].eval(x)) dq.pop_front(), m--;
      long long r = dq.front().eval(x) + (i + 1) * vec[i] - pfx[i];
      dp[i] = r;
    }
  }
  cout << dp.back() << endl;
}
