// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

using Int = long long;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}

template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}





template <typename T,bool isMin>

struct ConvexHullTrick {

  #define F first

  #define S second

  using P = pair<T, T>;

  deque<P> H;

  bool empty()const{return H.empty();}

  void clear(){H.clear();}



  inline Int sgn(T x){return x==0?0:(x<0?-1:1);}

  

  using D = long double;

  inline bool check(const P &a,const P &b,const P &c){

    if(b.S==a.S||c.S==b.S)

      return sgn(b.F-a.F)*sgn(c.S-b.S) >= sgn(c.F-b.F)*sgn(b.S-a.S);

    

    //return (b.F-a.F)*(c.S-b.S) >= (b.S-a.S)*(c.F-b.F);

    return

      D(b.F-a.F)*sgn(c.S-b.S)/D(abs(b.S-a.S)) >=

      D(c.F-b.F)*sgn(b.S-a.S)/D(abs(c.S-b.S));

  }  

  

  void addLine(T m,T b){

    if(!isMin) m*=-1,b*=-1;

    P line(m,b);

    if(empty()||H.front().F<=m){

      while(H.size()>=2&&check(line,H.front(),H[1])) H.pop_front();

      H.emplace_front(line);

    }else{

      assert(m<=H.back().F);      

      while(H.size()>=2&&check(H[H.size()-2],H.back(),line)) H.pop_back();

      H.emplace_back(line);

    } 

  }

  

  inline T getY(const P &a,const T &x){

    return a.F*x+a.S; 

  }



  T query(T x){

    assert(!empty());

    Int l=-1,r=H.size()-1;

    while(l+1<r){

      Int m=(l+r)>>1;

      if(getY(H[m],x)>=getY(H[m+1],x)) l=m;

      else r=m;

    }

    if(!isMin) return -getY(H[r],x);

    return getY(H[r],x);

  }



  T queryMonotoneFromLeft(T x){

    assert(!empty()); 

    while(H.size()>=2&&getY(H.front(),x)>=getY(H[1],x)) H.pop_front();

    if(!isMin) return -getY(H.front(),x);

    return getY(H.front(),x);

  }

  

  T queryMonotoneFromRight(T x){

    assert(!empty());

    while(H.size()>=2&&getY(H.back(),x)>=getY(H[H.size()-2],x)) H.pop_back();

    if(!isMin) return -getY(H.back(),x);

    return getY(H.back(),x);

  }

  

  T queryMonotoneInc(T x){

    if(!isMin) return queryMonotoneFromRight(x);

    return queryMonotoneFromLeft(x);

  }

  

  T queryMonotoneDec(T x){    

    if(!isMin) return queryMonotoneFromLeft(x);

    return queryMonotoneFromRight(x);

  }

  #undef F

  #undef S

};



//INSERT ABOVE HERE

signed main(){

  using CHT = ConvexHullTrick<Int, true>;

  Int s,n,m;

  cin>>s>>n>>m;

  vector<Int> x(s);

  for(Int i=0;i<s;i++) cin>>x[i];



  const Int MAX = 1e4+10;

  vector<Int> t(n),p(n);  

  for(Int i=0;i<n;i++) cin>>t[i]>>p[i],t[i]+=MAX,p[i]--;



  const Int INF = 1e15;

  vector<Int> dp(MAX*2,0),cnt(MAX*2,0);

  for(Int i=0;i<MAX*2;i++){

    for(Int j=0;j<n;j++){

      if(i+x[p[j]]<t[j]) dp[i]=INF;

      else dp[i]+=i+x[p[j]]-t[j],cnt[i]++;

    }

  }

  for(Int j=1;j<m;j++){

    vector<Int> nx(MAX*2,INF);

    CHT cht;

    for(Int i=MAX*2-1;i>=0;i--){

      cht.addLine(-i,dp[i]);

      nx[i]=cht.queryMonotoneDec(cnt[i])+i*cnt[i];

    }

    swap(dp,nx);

  }

  cout<<*min_element(dp.begin(),dp.end())<<endl;

  return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.422518984469929x):
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2603"



#include<bits/stdc++.h>

using namespace std;



#define call_from_test

#ifndef call_from_test

#include<bits/stdc++.h>

using namespace std;

using Int = long long;

#endif

//BEGIN CUT HERE

struct FastIO{

  FastIO(){

    cin.tie(0);

    ios::sync_with_stdio(0);

  }

}fastio_beet;

//END CUT HERE

#ifndef call_from_test

signed main(){

  return 0;

}

#endif



#ifndef call_from_test

#include<bits/stdc++.h>

using namespace std;

using Int = long long;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}

template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

#endif

//BEGIN CUT HERE

namespace MonotoneMinima{

  template<typename T,typename F>

  void induce(int l,int r,int a,int b,vector<int> &dp,F dist){

    if(l==r) return;

    int m=(l+r)>>1;

    int &idx=(dp[m]=a);

    T res=dist(m,idx);

    for(int i=a;i<b;i++){

      T tmp=dist(m,i);

      if(tmp<res) res=tmp,idx=i;

    }

    induce<T>(l,m,a,idx+1,dp,dist);

    induce<T>(m+1,r,idx,b,dp,dist);

  }



  // p < q -> argmin f(p, *) < argmin f(q, *)

  template<typename T,typename F>

  vector<int> args(int n,int m,F dist){

    vector<int> dp(n,-1);

    induce<T>(0,n,0,m,dp,dist);

    return dp;

  }

}

//END CUT HERE

#ifndef call_from_test

//INSERT ABOVE HERE

signed COLOPL2018FINAL_C(){

  cin.tie(0);

  ios::sync_with_stdio(0);

  using ll = long long;



  int n;

  cin>>n;

  vector<ll> as(n);

  for(int i=0;i<n;i++) cin>>as[i];



  auto dist=[&](int i,int j){return as[j]+(ll)(i-j)*(i-j);};

  auto res=MonotoneMinima::args<ll>(n,n,dist);



  for(int i=0;i<n;i++) cout<<dist(i,res[i])<<"\n";

  cout<<flush;

  return 0;

}

/*

  verified on 2019/10/29

  https://atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_c

*/

signed main(){

  //COLOPL2018FINAL_C();

  return 0;

}

#endif



#undef call_from_test



signed main(){

  int s,n,m;

  cin>>s>>n>>m;

  vector<int> xs(s);

  for(int i=0;i<s;i++) cin>>xs[i];



  vector<int> ts(n),ps(n);

  for(int i=0;i<n;i++) cin>>ts[i]>>ps[i],ps[i]--;



  vector<int> vs(n);

  for(int i=0;i<n;i++) vs[i]=ts[i]-xs[ps[i]];

  sort(vs.begin(),vs.end());



  vector<int> sm(n+1,0);

  for(int i=0;i<n;i++) sm[i+1]=sm[i]+vs[i];



  const int INF = 1e9;

  vector<int> dp(n+1,INF);

  dp[0]=0;

  for(int k=0;k<m;k++){

    auto dist=

      [&](int i,int j){

        return i<j?INF:dp[j]+(i?vs[i-1]:0)*(i-j)-(sm[i]-sm[j]);

      };

    auto res=MonotoneMinima::args<int>(n+1,n+1,dist);

    vector<int> nx(n+1);

    for(int i=0;i<=n;i++) nx[i]=dist(i,res[i]);

    swap(dp,nx);

  }

  cout<<dp[n]<<endl;

  return 0;

}