#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 dp(n, std::vector<int>(n, inf));

  auto get = [&](int l, int r) -> int {
    if (l > r) {
      return 0;
    }
    return dp[l][r];
  };

  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;
      }
    }
    for (int r = l; r < n; r++) {
      dp[l][r] = get(l + 1, r) + s[l] * c;
      for (int i = 0; i < m; i++) {
        dp[l][r] = std::min(dp[l][r], get(l + d[i], r) + sum[i][std::min(l + d[i] - 1, r)] + w[i]);
      }
    }
  }
  std::cout << dp[0][n - 1] << "\n";

  return 0;
}