I don't know!

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N, M, W, P;
cin >> N >> M >> W >> P;

vector<ll> w(N + 1);
for (int i = 1; i <= N; ++i) {
    cin >> w[i];
}

vector<vector<pair<int, int>>> adj(N + 1);
for (int i = 0; i < M; ++i) {
    int u, v, k;
    cin >> u >> v >> k;
    adj[u].emplace_back(v, k);
}

// Tarjan算法求强连通分量
int index = 0;
vector<int> indices(N + 1, -1), low(N + 1, -1);
vector<bool> onStack(N + 1, false);
stack<int> s;
vector<int> scc(N + 1, 0);
int scc_count = 0;

function<void(int)> tarjan = [&](int u) {
    indices[u] = low[u] = index++;
    s.push(u);
    onStack[u] = true;
    for (auto& edge : adj[u]) {
        int v = edge.first;
        if (indices[v] == -1) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (onStack[v]) {
            low[u] = min(low[u], indices[v]);
        }
    }
    if (low[u] == indices[u]) {
        scc_count++;
        while (true) {
            int v = s.top();
            s.pop();
            onStack[v] = false;
            scc[v] = scc_count;
            if (v == u) break;
        }
    }
};

for (int u = 1; u <= N; ++u) {
    if (indices[u] == -1) {
        tarjan(u);
    }
}

// 计算每个SCC的sum_w
vector<ll> sum_w(scc_count + 1, 0);
for (int u = 1; u <= N; ++u) {
    sum_w[scc[u]] += w[u];
}

// 处理缩点后的边的最小费用
vector<unordered_map<int, int>> min_edges(scc_count + 1);
for (int u = 1; u <= N; ++u) {
    for (auto& [v, k] : adj[u]) {
        int a = scc[u];
        int b = scc[v];
        if (a != b) {
            if (min_edges[a].find(b) == min_edges[a].end() || k < min_edges[a][b]) {
                min_edges[a][b] = k;
            }
        }
    }
}

// 构建缩点后的邻接表
vector<vector<pair<int, int>>> adj_scc(scc_count + 1);
for (int a = 1; a <= scc_count; ++a) {
    for (auto& [b, k] : min_edges[a]) {
        adj_scc[a].emplace_back(b, k);
    }
}

// 拓扑排序
vector<int> in_degree(scc_count + 1, 0);
for (int a = 1; a <= scc_count; ++a) {
    for (auto& [b, k] : adj_scc[a]) {
        in_degree[b]++;
    }
}

queue<int> q;
for (int a = 1; a <= scc_count; ++a) {
    if (in_degree[a] == 0) {
        q.push(a);
    }
}

vector<int> topo_order;
while (!q.empty()) {
    int a = q.front();
    q.pop();
    topo_order.push_back(a);
    for (auto& [b, k] : adj_scc[a]) {
        if (--in_degree[b] == 0) {
            q.push(b);
        }
    }
}

// 动态规划初始化
vector<vector<ll>> dp(scc_count + 1, vector<ll>(P + 1, -INF));
for (int a = 1; a <= scc_count; ++a) {
    dp[a][0] = sum_w[a];
}

// 动态规划转移
for (int a : topo_order) {
    for (auto& [b, k] : adj_scc[a]) {
        for (int p = 0; p <= P; ++p) {
            if (dp[a][p] == -INF) continue;

            // 不使用礼物券
            if (dp[b][p] < dp[a][p] + sum_w[b] - k) {
                dp[b][p] = dp[a][p] + sum_w[b] - k;
            }

            // 使用礼物券
            if (p < P) {
                if (dp[b][p + 1] < dp[a][p] + sum_w[b]) {
                    dp[b][p + 1] = dp[a][p] + sum_w[b];
                }
            }
        }
    }
}

// 计算最大收益
ll max_profit = -INF;
for (int a = 1; a <= scc_count; ++a) {
    for (int p = 0; p <= P; ++p) {
        if (dp[a][p] > max_profit) {
            max_profit = dp[a][p];
        }
    }
}

cout << W + max_profit << endl;

return 0;

}