A81675.奇怪的集市

$Alice$ 准备加入一个奇怪的集市，在这个集市中有一些奇怪的规则。

在集市中，有一些摊主，摊主们有一些关系，比如如果你给摊主 $u$ 元 ， 他可以把你推荐给他的一个朋友 $v_i$，需要支付费用 $k_i$;

同时集市中的人也是及其护短的，如果集市中的一些人，可以通过一些中介关系，任意两个人可以相互介绍到，我们把这些人当作一个小团体，在小团体中相互介绍，可以免除介绍费。

同时，如果说你拜访了集市中的某个人，如果是第一次拜访，可以获得 $w_i$ 元的礼物，

问 $Alice$ 现在带了 $W$ 元钱， 和 $P$ 件礼物，在一次操作中， $Alice$ 可以使用一个礼物免除介绍费， $Alice$ 选择在明天拜访这个集市，他可以从任意一个摊主开始，第一次拜访不需要介绍费。问经过一天的拜访，Alice 最多可以剩的多少钱？

• 第 1 行：四个整数，分别为摊主数量 $N$、推荐关系数量 $M$、初始预算 $W$、礼物券数量 $P$。
• 第 2 行：$N$ 个整数，第 $i$ 个为摊主 $i$ 的礼物价值 $w_i$。
• 接下来 $M$ 行：每行三个整数 $u,v,k$，表示一条从 $u$ 指向 $v$ 的推荐边，费用为 $k$。

输出一个整数，表示阿丽丝最多可以剩下多少钱。

数据范围

• $1 \le N \le 2\times10^{5}$
• $0 \le M \le 5\times10^{5}$
• $0 \le P \le 100$
• $0 \le w_i \le 10^{9}$
• $0 \le k_i \le 10^{9}$
• $0 \le W \le 10^{9}$
• 输入保证点编号为 $1\ldots n$。