#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; typedef long long ll; int main(){ int N,M; ll x; cin>>N>>M>>x; vector<int> C(N); vector<vector<ll>> X(5,vector<ll>(N+1,0)); for(int i=0;i<N;i++){ cin>>C[i]; C[i]--; X[C[i]][i+1]=1; } vector<vector<ll>> Y(5,vector<ll>(N+1,0)); for(int i=0;i<M;i++){ int a,b; ll y; cin>>a>>b>>y; b--; Y[b][N-a]+=y; } vector<vector<ll>> Z(5); for(int i=0;i<5;i++){ Z[i]=convolution_ll(X[i],Y[i]); } ll ANS=0; for(int i=0;i<=N;i++){ ANS=max(ANS,i*x+Z[0][N+i]+Z[1][N+i]+Z[2][N+i]+Z[3][N+i]+Z[4][N+i]); } cout<<ANS<<endl; }