虽然给出了图，但是和图没有太大关系。
首先可以想到一个非常朴素的 DP。
设 \(dp_{i,j}\) 表示当前占领到 \(i\)，拥有 \(j\) 个士兵的最大 \(\sum c\)。
那么转移就很显然了。
\(\begin{cases}dp_{i,j+b_i}\leftarrow dp_{i-1,j}\space(j\ge a_i)\\dp_{i,j}\leftarrow dp_{i,j+1}+c_{to}\space(i-to\text{ is connected})\end{cases}\)
枚举 \(i,j,to\)，时间复杂度 \(O(n^2m)\)，不能承受。
考虑进行优化。由于 \(to\) 是唯一一个状态内没出现的枚举量，从 \(to\) 方面优化。
想到一个贪心。对于每一个 \(to\)，显然是到最后能走的时候再走最优。
为什么？因为每一次占领不消耗士兵，而有限制 \(a_i\)，所以当前士兵越多越好。
也就是，不妨让士兵再走一段，来获得 \(b_i\) 个士兵，最后再走到 \(to\) 去。
所以预处理出每一个点最后由哪个点到达，再走就好了。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10, MAX = 5e3, inf = 1e9;
int n, m, k, lt[N], a[N], b[N], c[N], dp[N][N];
pair <int, int> fk[N];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n >> m >> k; for (int i = 1; i <= n; ++i)
cin >> a[i] >> b[i] >> c[i], lt[i] = i;
for (int i = 1, u, v; i <= m; ++i)
cin >> u >> v, lt[v] = max(lt[v], u);
for (int i = 1; i <= n; ++i) fk[i] = {lt[i], c[i]};
sort(fk + 1, fk + 1 + n);
for (int i = k + 1; i <= MAX; ++i) dp[0][i] = -inf;
int prev = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= MAX; ++j) dp[i][j] = -inf;
for (int j = a[i]; j <= MAX; ++j)
dp[i][j + b[i]] = max(dp[i][j + b[i]], dp[i - 1][j]);
while (prev <= n && fk[prev].first == i) {
for (int j = 0; j < MAX; ++j)
dp[i][j] = max(dp[i][j], dp[i][j + 1] + fk[prev].second);
++prev;
}
}
int res = -1;
for (int i = 0; i <= MAX; ++i) res = max(res, dp[n][i]);
cout << res << endl;
return 0;
}