นักชิม: หนึ่งวันคือการคูณเมทริกซ์หนึ่งครั้ง

// NOI 2020 "Delicacy" (programming.in.th 2041) - full constraints.
// (max,+) matrix exponentiation over a time-expanded graph.
//
// Every edge weight is 1..5, so split each city v into W copies (v,j),
// j = 0..W-1, where W = max edge weight.  State (v,j) means "I will land on
// city v in j more days".  (v,0) means "I am standing on v right now".
// One day = one application of the matrix A:
//     (u,0) --edge u->v of weight w--> (v, w-1)   gaining C[v]
//     (v,j) --> (v,j-1)  (j >= 1)                 gaining 0
// The reward C[v] is paid the moment the trip is committed; that is fine
// because a walk is only ever read off at a (x,0) state, where no trip is
// pending.
//
// Start vector: (1,0) = C[1], everything else unreachable.
// Advance day by day with binary lifting over A^(2^b); at each festival day t
// hop to day t, add y to the entry of state (x,0), continue.  Answer is the
// entry of (1,0) after exactly T days.
#include "dl_case.h"
#include <algorithm>
#include <vector>
#include <cstdio>

namespace dlfull {

using ll = long long;
static const ll NEG = -1000000000000000000LL;  // "unreachable"
static const ll HALF = -500000000000000000LL;  // anything <= HALF is unreachable
                                               // (every real value is >= 0)

struct MaxPlus {
    int S = 0;

    // C = A (max,+) B
    void mul(const std::vector<ll> &A, const std::vector<ll> &B, std::vector<ll> &C) const {
        for (int i = 0; i < S; i++) {
            ll *c = &C[(size_t)i * S];
            for (int j = 0; j < S; j++) c[j] = NEG;
            const ll *a = &A[(size_t)i * S];
            for (int k = 0; k < S; k++) {
                ll av = a[k];
                if (av <= HALF) continue;
                const ll *b = &B[(size_t)k * S];
                for (int j = 0; j < S; j++) {
                    ll t = av + b[j];
                    if (t > c[j]) c[j] = t;
                }
            }
            // Re-normalise: finite + NEG is still astronomically negative but
            // not exactly NEG; snapping it back stops it creeping upward over
            // the ~35 products we chain together.
            for (int j = 0; j < S; j++)
                if (c[j] <= HALF) c[j] = NEG;
        }
    }

    // out = v (max,+) B   (v is a row vector)
    void vmul(const std::vector<ll> &v, const std::vector<ll> &B, std::vector<ll> &out) const {
        for (int j = 0; j < S; j++) out[j] = NEG;
        for (int i = 0; i < S; i++) {
            ll av = v[i];
            if (av <= HALF) continue;
            const ll *b = &B[(size_t)i * S];
            for (int j = 0; j < S; j++) {
                ll t = av + b[j];
                if (t > out[j]) out[j] = t;
            }
        }
        for (int j = 0; j < S; j++)
            if (out[j] <= HALF) out[j] = NEG;
    }
};

ll solve(const Case &cs) {
    const int n = cs.n;
    const ll T = cs.T;

    int W = 1;
    for (const auto &e : cs.E) W = std::max(W, e[2]);

    MaxPlus mp;
    mp.S = n * W;
    const int S = mp.S;
    auto id = [&](int v, int j) { return v * W + j; };

    // A = one-day transition matrix.
    std::vector<ll> A((size_t)S * S, NEG);
    for (const auto &e : cs.E) {
        int u = e[0], v = e[1], w = e[2];
        ll &cell = A[(size_t)id(u, 0) * S + id(v, w - 1)];
        cell = std::max(cell, cs.C[v]);
    }
    for (int v = 0; v < n; v++)
        for (int j = 1; j < W; j++) A[(size_t)id(v, j) * S + id(v, j - 1)] = 0;

    // Binary powers of A up to the highest bit of T.
    int B = 0;
    while ((1LL << (B + 1)) <= T) B++;
    std::vector<std::vector<ll>> pw;
    pw.push_back(A);
    for (int b = 1; b <= B; b++) {
        std::vector<ll> nxt((size_t)S * S);
        mp.mul(pw[b - 1], pw[b - 1], nxt);
        pw.push_back(std::move(nxt));
    }

    std::vector<ll> vec((size_t)S, NEG), tmp((size_t)S);
    vec[id(0, 0)] = cs.C[0];  // day 0: standing on city 1, already eaten there

    auto advance = [&](ll d) {
        for (int b = 0; d > 0; b++, d >>= 1) {
            if (d & 1) {
                mp.vmul(vec, pw[b], tmp);
                vec.swap(tmp);
            }
        }
    };

    std::vector<std::array<ll, 3>> F = cs.F;
    std::sort(F.begin(), F.end(),
              [](const std::array<ll, 3> &a, const std::array<ll, 3> &b) { return a[0] < b[0]; });

    ll now = 0;
    for (size_t i = 0; i < F.size(); i++) {
        ll t = F[i][0];
        if (t > T || t < now) continue;  // defensive; the statement gives 1 <= t <= T
        advance(t - now);
        now = t;
        // Apply every festival held on day t.  Two festivals on the same day in
        // the same city stack; in different cities they simply land on
        // different states, which is exactly right.
        size_t j = i;
        while (j < F.size() && F[j][0] == t) {
            int x = (int)F[j][1];
            ll &cell = vec[id(x, 0)];
            if (cell > HALF) cell += F[j][2];
            j++;
        }
        i = j - 1;
    }
    advance(T - now);

    ll ans = vec[id(0, 0)];
    return ans <= HALF ? -1 : ans;
}

}  // namespace dlfull

#ifndef DL_NO_MAIN
int main() {
    Case cs = readCase();
    printf("%lld\n", dlfull::solve(cs));
    return 0;
}
#endif

// NOI 2020 "Delicacy" - subtask solver for T <= 52501 (also used as an oracle).
// Plain DP over days, written in pull form: dp[d][v] = best satisfaction for
// standing on city v on day d, already counting C[v] and any festival of day d.
// A cell asks every road u->v of length w where it could have come from:
//     dp[d][v] = max over roads (u, v, w) with w <= d of dp[d - w][u] + C[v]
#include "dl_case.h"
#include <algorithm>
#include <vector>
#include <cstdio>

namespace dlsub {

using ll = long long;
static const ll NONE = -1;  // unreachable (real values are always >= 0)

ll solve(const Case &cs) {
    const int n = cs.n;
    const ll T = cs.T;

    // roads grouped by destination city: (source, weight)
    std::vector<std::vector<std::pair<int, int>>> in(n);
    for (const auto &e : cs.E) in[e[1]].push_back({e[0], e[2]});

    // festivals bucketed by day
    std::vector<std::vector<std::pair<int, ll>>> fest((size_t)T + 1);  // (city, bonus)
    for (const auto &f : cs.F) {
        if (f[0] >= 0 && f[0] <= T) fest[(size_t)f[0]].push_back({(int)f[1], f[2]});
    }

    std::vector<std::vector<ll>> dp((size_t)T + 1, std::vector<ll>(n, NONE));
    dp[0][0] = cs.C[0];

    for (ll d = 0; d <= T; d++) {
        if (d > 0) {
            for (int v = 0; v < n; v++) {
                ll best = NONE;
                for (const auto &pr : in[v]) {
                    if (pr.second > d) continue;
                    ll from = dp[(size_t)(d - pr.second)][pr.first];
                    if (from == NONE) continue;
                    best = std::max(best, from + cs.C[v]);
                }
                dp[(size_t)d][v] = best;
            }
        }
        for (const auto &fb : fest[(size_t)d]) {
            if (dp[(size_t)d][fb.first] != NONE) dp[(size_t)d][fb.first] += fb.second;
        }
    }
    return dp[(size_t)T][0];  // NONE == -1, which is exactly the required output
}

}  // namespace dlsub

#ifndef DL_NO_MAIN
int main() {
    Case cs = readCase();
    printf("%lld\n", dlsub::solve(cs));
    return 0;
}
#endif

// NOI 2020 "Delicacy" - brute force for tiny cases.
// Literally enumerates every walk out of city 1: at each city pick an outgoing
// road, recurse, stop when day == T.  No DP table, no memoisation, no matrix -
// it shares nothing with the other two solvers except the input struct.
#include "dl_case.h"
#include <algorithm>
#include <vector>
#include <cstdio>

namespace dlbrute {

using ll = long long;

struct Runner {
    const Case *cs = nullptr;
    std::vector<std::vector<std::pair<int, int>>> adj;
    ll best = -1;

    ll bonusAt(ll day, int city) const {
        ll s = 0;
        for (const auto &f : cs->F)
            if (f[0] == day && (int)f[1] == city) s += f[2];
        return s;
    }

    void rec(ll day, int city, ll sum) {
        if (day == cs->T) {
            if (city == 0 && sum > best) best = sum;
            return;
        }
        for (const auto &pr : adj[city]) {
            ll nd = day + pr.second;
            if (nd > cs->T) continue;
            rec(nd, pr.first, sum + cs->C[pr.first] + bonusAt(nd, pr.first));
        }
    }
};

ll solve(const Case &cs) {
    Runner r;
    r.cs = &cs;
    r.adj.assign(cs.n, {});
    for (const auto &e : cs.E) r.adj[e[0]].push_back({e[1], e[2]});
    r.rec(0, 0, cs.C[0] + r.bonusAt(0, 0));
    return r.best;
}

}  // namespace dlbrute

#ifndef DL_NO_MAIN
int main() {
    Case cs = readCase();
    printf("%lld\n", dlbrute::solve(cs));
    return 0;
}
#endif

// Shared *data* declaration only (no algorithm code) so that the three
// independent solvers can be linked into one stress-test binary verbatim.
#ifndef DL_CASE_H
#define DL_CASE_H
#include <vector>
#include <array>
#include <cstdio>

struct Case {
    int n = 0, m = 0, k = 0;
    long long T = 0;
    std::vector<long long> C;                // C[i], cities 0-indexed
    std::vector<std::array<int, 3>> E;       // {u, v, w}, cities 0-indexed
    std::vector<std::array<long long, 3>> F; // {t, x, y}, x 0-indexed
};

inline Case readCase() {
    Case c;
    long long T = 0;
    if (scanf("%d %d %lld %d", &c.n, &c.m, &T, &c.k) != 4) return c;
    c.T = T;
    c.C.assign(c.n, 0);
    for (int i = 0; i < c.n; i++) {
        if (scanf("%lld", &c.C[i]) != 1) return c;
    }
    c.E.assign(c.m, {0, 0, 0});
    for (int i = 0; i < c.m; i++) {
        int u = 0, v = 0, w = 0;
        if (scanf("%d %d %d", &u, &v, &w) != 3) return c;
        c.E[i] = {u - 1, v - 1, w};
    }
    c.F.assign(c.k, {0, 0, 0});
    for (int i = 0; i < c.k; i++) {
        long long t = 0, x = 0, y = 0;
        if (scanf("%lld %lld %lld", &t, &x, &y) != 3) return c;
        c.F[i] = {t, x - 1, y};
    }
    return c;
}
#endif