import bisect
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    n = int(data[ptr])
    ptr += 1
    m = int(data[ptr])
    ptr += 1
    x = int(data[ptr])
    ptr += 1
    
    C = list(map(int, data[ptr:ptr+n]))
    ptr += n
    
    sum_ab = defaultdict(lambda: defaultdict(int))
    for _ in range(m):
        a = int(data[ptr])
        ptr += 1
        b = int(data[ptr])
        ptr += 1
        y = int(data[ptr])
        ptr += 1
        sum_ab[a][b] += y
    
    # Preprocess positions for each color (1-based)
    positions = [[] for _ in range(6)]  # colors 1-5
    for idx in range(n):
        c = C[idx]
        positions[c].append(idx + 1)  # 1-based position
    
    total = [0] * (n + 1)  # total[K] for K from 0 to n
    
    # Iterate through all a and c in sum_ab
    for a in list(sum_ab.keys()):
        for c in list(sum_ab[a].keys()):
            y_sum = sum_ab[a][c]
            if y_sum == 0:
                continue
            pos_list = positions[c]
            if not pos_list:
                continue
            # Find the first position >= a
            idx = bisect.bisect_left(pos_list, a)
            for i in range(idx, len(pos_list)):
                pos = pos_list[i]
                K = pos - a
                if K > n:
                    break  # pos <=n, so K = pos -a <=n -a <=n
                total[K] += y_sum
    
    max_score = 0
    for K in range(n + 1):
        current = x * K + total[K]
        if current > max_score:
            max_score = current
    print(max_score)

if __name__ == "__main__":
    main()