func_code_string: #include <bits/stdc++.h>   using namespace std;   const long long oo = 1LL << 55;   const int MAX_N = 100005;   const int MAX_M = 100005;   const int MAX_P = 105;   template <class T>   class Deque {    public:     Deque() { Clear(); }     void Clear() { front = 1, back = 0; }     void PushBack(const T x) { values[++back] = x; }     void PopBack() { --back; }     void PopFront() { ++front; }     T Front() const { return values[front]; }     T Back() const { return values[back]; }     bool Empty() const { return front > back; }     int Size() const { return back - front + 1; }     T &operator[](const int index) { return values[front + index]; }       private:     T values[MAX_M];     int front, back;   };   class Line {    public:     long long m, n;     Line() {}     Line(const long long m, const long long n) {       this->m = m;       this->n = n;     }     long long Value(const long long x) const { return m * x + n; }     static double Intersect(const Line &L1, const Line &L2) {       return (1.0 * L2.n - L1.n) / (1.0 * L1.m - L2.m);     }   };   int N, M, P, D[MAX_N], T[MAX_M];   long long SumT[MAX_M], DP[2][MAX_M], Solution;   void Preprocess() {     T[0] = 0;     sort(T + 1, T + M + 1);     SumT[0] = 0;     for (int i = 1; i <= M; ++i) SumT[i] = SumT[i - 1] + T[i];   }   void Solve() {     Preprocess();     DP[0][0] = 0;     for (int i = 1; i <= M; ++i) DP[0][i] = 1LL * T[i] * i - SumT[i];     for (int p = 2; p <= P; ++p) {       Deque<Line> deq;       for (int i = p; i <= M; ++i) {         Line L = Line(-(i - 1), SumT[i - 1] + DP[0][i - 1]);         while (deq.Size() > 1 &&                Line::Intersect(deq[deq.Size() - 1], L) <                    Line::Intersect(deq[deq.Size() - 2], deq[deq.Size() - 1]))           deq.PopBack();         deq.PushBack(L);         while (deq.Size() > 1 && Line::Intersect(deq[0], deq[1]) < 1.0 * T[i])           deq.PopFront();         DP[1][i] = deq.Front().Value(T[i]) + 1LL * i * T[i] - SumT[i];       }       memcpy(DP[0], DP[1], sizeof(DP[1]));     }     Solution = DP[0][M];   }   void Read() {     cin >> N >> M >> P;     D[1] = 0;     for (int i = 2; i <= N; ++i) {       cin >> D[i];       D[i] += D[i - 1];     }     for (int i = 1; i <= M; ++i) {       int h, t;       cin >> h >> t;       T[i] = t - D[h];     }   }   void Print() { cout << Solution <<   n ; }   int main() {     Read();     Solve();     Print();     return 0;   }   