#include <iostream>
#include <vector>
#include <climits>
using namespace std;
constexpr int maxn = 150;
int n, m, c, maxTime = 0;
vector<int> s;

int main() {
    cin >> n >> m >> c;
    s.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        maxTime = max(maxTime, s[i]);
    }
    //骑行时间的前缀和数组
    vector<vector<int> > sumTime(maxTime + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= maxTime; i++) {
        for (int j = 1; j <= n; j++) {
            sumTime[i][j] = sumTime[i][j - 1] + (max(s[j] - i + 1,0));
        }
    }
    //处理骑行卡
    vector<vector<int> > infoCard(maxn + 1, vector<int>(n + 1,INT_MAX/2));
    for (int i = 1; i <= m; i++) {
        int w, d, t;
        cin >> w >> d >> t;
        infoCard[min(t,maxTime)][d] = min(w, infoCard[min(t,maxTime)][d]);
    }
    for (int i = 1; i <= maxTime; i++) {
        for (int j = n - 1; j >= 1; j--) {
            infoCard[i][j] = min(infoCard[i][j], infoCard[i][j + 1]);
        }
    }
    //动态规划
    vector<vector<vector<int> > > dpArray(maxTime + 1, vector<vector<int> >(n + 1, vector<int>(n + 1,INT_MAX/2)));
    vector<vector<vector<int> > > dpTMPArray(maxTime + 1, vector<vector<int> >(n + 1, vector<int>(n + 1,INT_MAX/2)));
    for (int i = maxTime; i >= 1; i--) {
        for (int l = n; l >= 1; l--) {
            for (int r = l; r <= n; r++) {
                dpArray[i][l][r] = (sumTime[i][r] - sumTime[i][l - 1]) * c;
                if (i==maxTime)dpTMPArray[i][l][r]=infoCard[i][r-l+1];
                else dpTMPArray[i][l][r] = min(dpTMPArray[i+1][l][r],infoCard[i][r-l+1]+dpArray[i + 1][l][r]);
                for (int x = l; x <= r; x++) {
                    for (int y = x + 1; y <= r; y++) {
                        int tmp = 0;
                        if (x - 1 >= l)tmp += dpArray[i][l][x - 1];
                        if (y <= r)tmp += dpArray[i][y][r];
                        dpArray[i][l][r] = min(tmp+dpTMPArray[i][x][y-1], dpArray[i][l][r]);
                        // for (int j = i; j <= maxTime; j++) {
                        //     int ttmp = tmp + infoCard[j][y - x];
                        //     if (j != maxTime) {
                        //         ttmp += dpArray[j + 1][x][y - 1];
                        //     }
                        //     dpArray[i][l][r] =min( ttmp,dpArray[i][l][r]);
                        // }
                    }
                }
            }
        }
    }
    cout << dpArray[1][1][n] << endl;
    return 0;
}