dp

我在一开始的时候也想要用dp去做，但是发现，对于占据一个节点
我们可以在当前位置占据他，也可以在之后占据他。
这一就意味着我峨嵋你的dp具有后效性，那么就不能dp了

苦恼啊苦恼。
后来发现，这里其实是一个简单的贪心。

对于占据一个节点，很明显我们在能占据他的节点中的最后面占据他就好了！
这个贪心至关重要，他帮助了我们解决了dp的后效性问题。
那么我们就可以利用dp了。
dp[i][j]到第i个位置上，拥有j个士兵(还没在当前节点招募士兵)从这之后的最大收益。

很明显，我们可以不去防守节点，直接去占据下一个节点。
当饭我们也可以去占据节点。如何占据呢？
我们从大到小的占据，优先占据性价比最高的嘛。

如此，我们便完成了！！！！
真的是，如果没有意识到那个贪心真的是很难做出来的！！！！！

#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
const int max_n = 5500;
typedef long long ll;
const ll inf = 1e9;
int n,m,k;
ll a[5500],b[5500],c[5500];
int last[max_n];
int dp[5500][5500];
bool vis[5500][5500];
vector<int> G[5500];
ll Solve(int ii,int jj){
    if (vis[ii][jj])return dp[ii][jj];
    vis[ii][jj]=true;
    if (jj<a[ii])return dp[ii][jj]=-inf;
    if (ii==n+1)return dp[ii][jj]=0;
    ll ans = Solve(ii+1,jj+b[ii]);
    ll sum = 0;
    for (int i=0;i<G[ii].size();++i){
        sum += G[ii][i];
        if (jj-i-1+b[ii]<0)break;
        ans = max(ans,Solve(ii+1,jj-i-1+b[ii])+sum);
    }return dp[ii][jj]=ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>k;
    for (int i=1;i<=n;++i)cin>>a[i]>>b[i]>>c[i];
    for (int i=1;i<=n;++i)last[i]=i;
    for (int i=1;i<=m;++i){
        int u,v;cin>>u>>v;
        if (u>v)swap(u,v);
        last[u]=max(last[u],v);
    }
    for (int i=1;i<=n;++i)G[last[i]].push_back(c[i]);
    for (int i=1;i<=n;++i)sort(G[i].begin(),G[i].end(),greater<ll>());

    ll ans = Solve(1,k);
    if (ans<0)cout<<-1<<endl;
    else cout<<ans<<endl;
}