#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
	int X=0; char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X;
}

const int N=250+10,K=200+10;

int n,m,T,k,c[N];
int id[N][6],tot;

struct festival { int t,x,y; } t[K];
bool operator <(festival a,festival b) { return a.t<b.t; }

struct Matrix {
	ll s[N][N];
	Matrix() { memset(s,0xc0,sizeof(s)); }
	ll* operator [](int i) { return s[i]; }
} Q[31];
ll A[N];
Matrix operator *(Matrix a,Matrix b) {
	Matrix c;
	for (int i=1;i<=tot;++i)
		for (int k=1;k<=tot;++k) {
			if (a[i][k]<0) continue;
			for (int j=1;j<=tot;++j)
				c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
		}
	return c;
}
void Mul(Matrix Q) {
	static ll B[N];
	for (int i=1;i<=tot;++i) B[i]=-4e18;
	for (int k=1;k<=tot;++k) {
		if (A[k]<0) continue;
		for (int j=1;j<=tot;++j)
			B[j]=max(B[j],A[k]+Q[k][j]);
	}
	for (int i=1;i<=tot;++i) A[i]=B[i];
}

int main() {
	tot=n=read(),m=read(),T=read(),k=read();
	for (int i=1;i<=n;++i) c[i]=read();
	for (int i=1;i<=n;++i) id[i][0]=i;
	for (int i=1;i<=m;++i) {
		int u=read(),v=read(),w=read();
		for (int j=1;j<w;++j) if (!id[u][j]) id[u][j]=++tot;
		for (int j=1;j<w;++j) Q[0][id[u][j-1]][id[u][j]]=0;
		Q[0][id[u][w-1]][v]=c[v];
	}
	for (int i=1;i<=k;++i) t[i]=(festival){read(),read(),read()};
	sort(t+1,t+k+1); t[0]=(festival){0,0,0},t[k+1]=(festival){T,0,0};
	for (int i=1;i<=30;++i) Q[i]=Q[i-1]*Q[i-1];
	for (int i=2;i<=tot;++i) A[i]=-4e18; A[1]=c[1];
	for (int i=1;i<=k+1;++i) {
		int dt=t[i].t-t[i-1].t;
		for (int j=30;~j;--j) if (dt&(1<<j)) Mul(Q[j]);
		A[t[i].x]+=t[i].y;
	}
	if (A[1]<0) puts("-1");
	else printf("%lld\n",A[1]);
	return 0;
}

一眼瞪出 dp 方程

$$f_{T,v}=c_v+\sum_i[t_i=T][x_i=v]y_i+\max_{(u,v,w)\in E}\{f_{T-w,u}\} $$

显然直接 dp 是不行的，于是考虑矩阵快速幂优化。

当然矩阵乘法显然是指 max-plus 矩阵乘法，以下记为 $\times_{\max}^+$ 或 $\times$。

先处理 $k=0$ 的情况。

$$f_{T,v}=c_v+\max_{(u,v,w)\in E}\{f_{T-w,u}\}$$

这个 $w$ 未必为 $1$，阻碍了矩阵快速幂！

这不好。

注意到 $1\le w\le5$。

记 $Y=\max\{w\}$。

因此设

$${\bf f}_T=(f_{T,1},f_{T,2},\dots,f_{T,n},f_{T-1,1},f_{T-1,2},\dots,f_{T-Y+1,n})' $$

规定可行性的转移矩阵 $W$ 满足

$$W_{ji}=\begin{cases} [\exist_{(u,v,w)\in E}j=v\land i=u+(w-1)n]&j\le n\\ [i=j-n]&j>n \end{cases} $$

注意这里定义艾弗森约定 $[A]=\begin{cases}0&A为真\\-\infty&A为假\end{cases}$

规定对角阵

$$\operatorname{diag}_{n}\{d_1,d_2,d_3,\dots,d_n\}=(d_i+[i=j])_{n\times n} $$

定义权值矩阵

$$V=\operatorname{diag}_{Yn}\{c_1,c_2,\dots,c_n,0,0,\dots,0\} $$

则

$${\bf f}_T=(V\times W)^T\times{\bf f}_0$$

（注意 ${\bf f}_0$ 定义时已把 $1$ 号点权值算入）

复杂度 $O((nY)^3\log T)$。

---

考虑如何解决 $k\neq0$ 的情况。

先不妨令 $t_k$ 单调不减。

定义事件矩阵

$$S_k=\operatorname{diag}_{Yn}\{{\begin{cases}y_k&x_k=i\\0&x_k\neq i\end{cases}}\} $$

然后即有

$${\bf g}_k=S_k\times(V\times W)^{t_k-t_{k-1}}\times{\bf g}_{k-1} $$

其中记 ${\bf g}_0={\bf f}_0,{\bf g}_{k+1}={\bf f}_T,S_{k+1}=\operatorname{diag}_{Yn}\{0,0,\dots,0\}$。

然后就随便做了。矩阵快速幂即可。

复杂度 $O((nY)^3k\log T)$。

---

然后每步计算出的矩阵只有第一列有用，二进制预处理后稍微优化一下就好了。

复杂度 $O((nY)^3\log T+(nY)^2k\log T)$。

最后这一步优化没想到。qwq