fork download
  1. //****** @mdazmat9 **********
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define int long long
  5. #define UB upper_bound
  6. #define LB lower_bound
  7. #define BS binary_search
  8. #define EB emplace_back
  9. #define PB push_back
  10. #define endl "\n"
  11. #define MOD 1000000007
  12. #define MOD2 998244353
  13. #define F first
  14. #define S second
  15. #define ALL(a) (a).begin(),(a).end()
  16. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  17. int fast_pow(int x, int y, int p);
  18. map<int,vector<pair<int,int>>> save;
  19. class Node{
  20. public:
  21. int a,b,profit;
  22. };
  23. Node node[5001];
  24. int dp[5001][5001];
  25. int n;
  26. int rec(int pos,int k){
  27. if(pos==n){
  28. return 0;
  29. }
  30. if(dp[pos][k]!=-1){
  31. return dp[pos][k];
  32. }
  33. int ans=INT_MIN;
  34. if(k>=node[pos].a){
  35. k+=node[pos].b;
  36. ans=max(ans,rec(pos+1,k));
  37. int cnt=1;
  38. int temp=0;
  39. for(auto x:save[pos]){
  40. if(k-cnt>=0){
  41. temp+=x.F;
  42. ans=max(ans,temp+rec(pos+1,k-cnt));
  43. cnt++;
  44. }
  45. }
  46. }
  47. return dp[pos][k]=ans;
  48. }
  49.  
  50. void solve() {
  51. int m,k;cin>>n>>m>>k;
  52. for(int i=0;i<n;i++){
  53. cin>>node[i].a>>node[i].b>>node[i].profit;
  54. }
  55. map<int,int> mp;
  56. for(int i=0;i<m;i++){
  57. int u,v;cin>>u>>v;
  58. u--;v--;
  59. mp[v]=max(mp[v],u);
  60. }
  61. for(int i=0;i<n;i++){
  62. mp[i]=max(i,mp[i]);
  63. }
  64. for(auto x:mp){
  65. save[x.S].EB(node[x.F].profit,x.F);
  66. }
  67.  
  68. for(auto& x:save){
  69. sort(ALL(x.S),greater<pair<int,int>>());
  70. }
  71. memset(dp,-1, sizeof(dp));
  72. cout<<max(-1ll,rec(0,k))<<endl;
  73.  
  74. }
  75. int32_t main() {
  76. IOS;
  77. int test = 1;
  78. // cin >> test;
  79. for(int i=1;i<=test;i++){
  80. solve();
  81. }
  82. return 0;
  83. }
  84. int fast_pow(int x, int y, int p) {
  85. int res = 1;
  86. x = x % p;
  87. while (y > 0) {
  88. if (y & 1)
  89. res = (res * x) % p;
  90. y = y >> 1;
  91. x = (x * x) % p;
  92. }
  93. return res;
  94. }
Success #stdin #stdout 0.05s 198992KB
stdin
Standard input is empty
stdout
0