import cmath
pi = cmath.pi
exp = cmath.exp


def make_exp_t(N, base):
  exp_t = {0: 1}
  temp = N
  while temp:
    exp_t[temp] = exp(base / temp)
    temp >>= 1
  return exp_t


def fft_dfs(f, s, N, st, exp_t):
  if N == 2:
    a = f[s]; b = f[s + st]
    return [a + b, a - b]
  N2 = N // 2; st2 = st * 2
  F0 = fft_dfs(f, s, N2, st2, exp_t)
  F1 = fft_dfs(f, s + st, N2, st2, exp_t)
  w = exp_t[N]; wk = 1.0
  for k in range(N2):
    U = F0[k]; V = wk * F1[k]
    F0[k] = U + V
    F1[k] = U - V
    wk *= w
  F0.extend(F1)
  return F0


def fft(f, N):
  if N == 1:
    return f
  return fft_dfs(f, 0, N, 1, fft_exp_t)


def ifft(F, N):
  if N == 1:
    return F
  f = fft_dfs(F, 0, N, 1, ifft_exp_t)
  for i in range(N):
    f[i] /= N
  return f


n, m, x = map(int, input().split())
c = list(map(int, input().split()))
color = [[0] * n for _ in range(5)]
point = [[0] * n for _ in range(5)]
for i in range(n):
  color[c[i] - 1][i] += 1
for _ in range(m):
  a, b, y = map(int, input().split())
  point[b - 1][n - a] += y

N = 2**(2 * len(color[0]) - 1).bit_length()
fft_exp_t = make_exp_t(N, -2j * pi)
ifft_exp_t = make_exp_t(N, 2j * pi)

score_f = []
for i in range(5):
  f = color[i]
  g = point[i]
  f.extend([0] * (N - len(f)))
  g.extend([0] * (N - len(g)))
  F = fft(f, N)
  G = fft(g, N)
  fg = ifft([a * b for a, b in zip(F, G)], N)[n - 1:]
  score_f.append(list(map(lambda x: int(x.real + 0.5), fg)))
score = [
  score_f[0][i] + score_f[1][i] + score_f[2][i] + score_f[3][i] + score_f[4][i]
  for i in range(n)]

ans = x * n
for i in range(n):
  ans = max(ans, i * x + score[i])
print(ans)