#include <bits/stdc++.h>

using i64 = long long;

constexpr int inf = 1E9;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, m, c;
  std::cin >> n >> m >> c;

  std::vector<int> s(n);
  for (int i = 0; i < n; i++) {
    std::cin >> s[i];
  }

  std::vector<int> w(m), d(m), t(m);
  for (int i = 0; i < m; i++) {
    std::cin >> w[i] >> d[i] >> t[i];
  }

  std::vector<int> f(n + 1, inf);
  f[n] = 0;

  for (int l = n - 1; l >= 0; l--) {
    std::vector sum(m, std::vector<int>(n));
    for (int i = 0; i < m; i++) {
      for (int r = l; r < l + d[i] && r < n; r++) {
        sum[i][r] = (l == r ? 0 : sum[i][r - 1]) + std::max(0, s[r] - t[i]) * c;
      }
    }
    f[l] = f[l + 1] + s[l] * c;
    for (int i = 0; i < m; i++) {
      for (int j = 1; j <= d[i] && l + j <= n; j++) {
        f[l] = std::min(f[l], f[l + j] + sum[i][l + j - 1] + w[i]);
      }
    }
  }
  std::cout << f[0] << "\n";

  return 0;
}