import bisect
from collections import defaultdict

n, m, X = map(int, input().split())
C = list(map(int, input().split()))

# Preprocess positions for each color (1-based index)
pos = [[] for _ in range(6)]  # colors 1-5
for idx, c in enumerate(C, 1):  # idx is 1-based
    pos[c].append(idx)

sum_ab = defaultdict(int)
for _ in range(m):
    a, b, y = map(int, input().split())
    sum_ab[(a, b)] += y

Y = [0] * (n + 1)  # Y[k] for k in 0..n

# Process each (a, b) group and accumulate the contributions
for (a, b), total in sum_ab.items():
    if total == 0:
        continue
    pb = pos[b]
    if not pb:
        continue
    # Find the first index in pb that is >= a using bisect
    idx = bisect.bisect_left(pb, a)
    for i in pb[idx:]:
        k = i - a
        if 0 <= k <= n:
            Y[k] += total

# Compute the maximum score
max_score = 0
for k in range(n + 1):
    current_score = X * k + Y[k]
    if current_score > max_score:
        max_score = current_score

print(max_score)