问题具有显著的阶段性，考虑 DP，设 $f_i$ 表示前 $i$ 个人操作后造成的最大伤害。

首先有直接攻击的转移 $f_i \gets f_{i - 1} + d_{b_i}$。在此之外，我们还可以找到一个 $(p_j, q_j, c_j)$，并且找到一个 $k < i$，使得 $a_k = p_j, b_i = q_j$，转移为 $f_i \gets f_{k - 1} + c_j + d_{b_i}$。

考虑记 $s_{q_j} = \{(p_j, c_j)\}, u_{p_j} = \max_{a_k = p_j} \{f_{k - 1}\}$，每次枚举 $(p_j, c_j) \in s_{b_i}$ 并转移 $f_i \gets u_{p_j} + c_j + d_{b_i}$ 即可。$\mathcal{O}(1)$ 维护 $u_{p_j}$ 是简单的。时间复杂度 $\mathcal{O}(|s_i| + 1)$，可以达到 $\mathcal{O}(m)$，不能通过。

我们注意到满足 $|s_{q_j}| > B$ 的 $q_j$ 一定不超过 $\frac{m}{B}$ 个。考虑仅在 $\{s_i\}$ 中保留 $|s_{q_j}| \leq B$ 的 $s_{q_j}$，这时上述转移复杂度降到 $\mathcal{O}(B)$；而对于剩下的 $(p_j, q_j, c_j)$ 记 $t_{p_j} = \{(q_j, c_j)\}$，那么一定有 $|t_i| \leq \frac{n}{B}$。

仅对于在 $t_{p_j}$ 中的 $(p_j, q_j, c_j)$ 设 $v_{q_j} = \max_{(p_j, q_j, c_j), a_k = p_j} \{f_{k - 1} + c_j\}$，转移时直接 $f_i \gets v_{b_i} + d_{b_i}$ 即可。维护 $v_{q_j}$ 可以枚举 $(q_j, c_j) \in t_{a_i}$，有 $v_{q_j} \gets f_{i - 1} + c_j$，时间复杂度 $\mathcal{O}(|t_i|) = \mathcal{O}(\frac{m}{B})$。总时间复杂度 $\mathcal{O}(1 + \frac{m}{B}) = \mathcal{O}(\frac{m}{B})$。

综上，时间复杂度为 $\mathcal{O}(n(B + \frac{m}{B}))$，显然 $B = \sqrt m$ 时取得最小值 $\mathcal{O}(n\sqrt m)$。

这一方法是一种似乎并不常见的动态规划优化，称为根号分治优化 DP，有较高的思维难度。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 2e5 + 10, maxm = 2e5 + 10, maxx = 2e5 + 10, maxy = 2e5 + 10, gap = 5e2;

int n, m, x, y;
int d[maxx], a[maxn], b[maxn], p[maxm], q[maxm], c[maxm], cnt[maxx];
long long u[maxy], v[maxx], f[maxn];
vector<pair<int, int> > s[maxx], t[maxy];

int main(){
    scanf("%d %d %d %d", &n, &m, &x, &y);
    for (int i = 1; i <= x; i++){
        scanf("%d", &d[i]);
    }
    for (int i = 1; i <= n; i++){
        scanf("%d %d", &a[i], &b[i]);
    }
    for (int i = 1; i <= m; i++){
        scanf("%d %d %d", &p[i], &q[i], &c[i]);
        cnt[q[i]]++;
    }
    for (int i = 1; i <= m; i++){
        if (cnt[q[i]] > gap){
            t[p[i]].emplace_back(q[i], c[i]);
        }else{
            s[q[i]].emplace_back(p[i], c[i]);
        }
    }
    mem(u, -0x3f), mem(v, -0x3f);
    for (int i = 1; i <= n; i++){
        f[i] = f[i - 1] + d[b[i]];
        if (cnt[b[i]] > gap){
            f[i] = max(f[i], v[b[i]] + d[b[i]]);
        }else{
            for (auto x: s[b[i]]){
                f[i] = max(f[i], u[x.first] + x.second + d[b[i]]);
            }
        }
        u[a[i]] = max(u[a[i]], f[i - 1]);
        for (auto x: t[a[i]]){
            v[x.first] = max(v[x.first], f[i - 1] + x.second);
        }
    }
    printf("%lld", f[n]);

return 0;
}